从头再来！社招找工作——算法题复习九：动态规划

动态规划

本专栏已经介绍了很多基础的数据结构、经典算法和思想，终于来到了本篇介绍动态规划的博客。相信很多初次学习算法题的朋友们会谈“动态规划”色变，总是理解不了它的内涵，无法运用动态规划的思想来解题，久而久之一听说某道题需要用到“动态规划”就直接pass掉。希望通过本篇博客，大家可以（1）理解什么是动态规划，什么样的情况适合用动态规划解题；（2）如何利用动态规划解题；（3）（可选）在写出基础性的动态规划解题方案之后，进一步优化直到实现最简化、最简洁的代码。

按我的理解，动态规划适合用于这类题目：这类题目有多个时刻/多个步骤/多个数字组成的一维数组或者二维数组，且易得初始时刻/初始状态/数组下标为0或者(0,0)的某种极值（可以是极大值，也可以是极小值），且有一套递推公式从初始时刻/初始状态/数组下标为0或者(0,0)的数值推到下一时刻/下一状态/数组下一个位置，并最终得到最后时刻/最后状态/最大坐标的值，和全部时刻/全部状态/数组全部值中的全局最优解。这种题目，就一定可以由动态规划来解的。
找到初始条件应该还算简单，所以动态规划的难点其实就是两个：（1）确定我们要将什么东西作为极值？这也将影响到第二点（2）递推公式如何求出？另外，如果还想让面试官眼前一亮，或者使得代码简洁、优雅、占用额外空间少，学有余力的朋友们可以思考如何优化动态规划。
接下来，我将通过许多例题，来向大家展示动态规划题目的分析、解题过程。

斐波那数列

首先来道开胃小凉菜，凉到不能再凉的斐波那切数列：给定一个数字n，求斐波那切数列中第n位数字。
我们在递归这篇博客里已经介绍过，用递归来解的话会造成很大的资源浪费，并提到了正确的解法是动态规划，那么我们以此来看看是如何动态规划的：
首先找初始状态，显然这里有两个nums[0]=0和nums[1]=1；要确定的极值呢，这里其实简化成为了一个普通数值，也就是数列第i项的值；递推公式更是现成给出的nums[i+2] = nums[i] + nums[i+1]。那么直接得到代码，注意看注释：

public int Fibonacci(int n) {if (n <= 2) {return n - 1; // 特殊情况}int[] f = new int[n]; // 构建数组，里面的值是“数列第i+1项的值”f[0] = 0;f[1] = 1; // 初始状态for (int i = 2;i < n;i++) {f[i] = f[i-2] + f[i-1]; // 递推公式}return f[n-1]; // 得到结果
}

怎么样，这样写出来是不是很明晰，动态规划其实就是这么一个流程。
那么我们考虑一下如何简洁。这里我们用到了一个一维数组，且实际上我们要求得一个新值只需要用到的前面两个旧值。所以我们直接用两个数字，来替换数组，即：

public int Fibonacci(int n) {if (n <= 2) {return n - 1;}int a = 0;int b = 1;for (int i = 2;i < n;i++) {// 用两个数字来代替一整个数组，辗转腾挪int c = a + b;a = b;b = c;}return b;
}

我们用两个数字实现了对数组的降维，空间复杂度由O(n)降到了O(1)，大大优化代码。

跳台阶

跳台阶/爬楼梯

牛客网
Leetcode
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
我们来分析一下这个题目如何用动态规划来解：首先找初始状态，如果台阶只有1级，那么显然青蛙只有1种跳法；如果台阶只有2级，青蛙只有2种跳法，这是我们易得的两种初始状态。
再来看我们需要的值是什么，这个也好找，就是跳到第 n 级台阶的跳法个数。
接着来看递推公式。如果想要跳到第 i 级台阶，跳法只有两种：只有从第 i-1 级跳1级，或者从第 i-2 级跳2级，那么第 i 级的跳法次数就应该等于第 i-1 级的次数加上第 i-2 级的次数，因此得到递推式nums[i] = nums[i-1] + nums[i-2]。
Wait!!!这个递推式怎么和斐波那契数列一样！其实这道题就是斐波那契数列的衍生题，只不过初始条件有些不同。我们直接给出简化版本的题解代码：

public int jumpFloor(int n) {if (n <= 2) {return n;}int a = 1;int b = 2;for (int i = 2;i < n;i++) {// 用两个数字来代替一整个数组，辗转腾挪int c = a + b;a = b;b = c;}return b;
}

最小花费跳台阶

牛客网
给定一个整数数组 cost，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。

本题是在上一题的基础上增加了一个爬楼梯成本，但显然还是由动态规划来做的。首先，初始状态依然是找特殊情况，如果要爬到第0级台阶那么成本为0，爬到第1级也是0；其次，这里需要设计一个级值，即创建一个数组 sum，sum[i] 表示爬到第 i 级台阶的最低花费。然后来看递推公式，如果是爬到第 i 级（i != 0 and i != 1），则有sum[i] = min{ sum[i-1]+cost[i-1], sum[i-2]+cost[i-2]}。由此得出代码：

public int minCostClimbingStairs (int[] cost) {int len = cost.length;if (len <= 2) {return 0;}int[] sum = new int[len+1]; // sum[i] 表示爬到第 i 级台阶的最低花费sum[0] = 0;sum[1] = 0; // 初始状况for (int i = 2;i <= len;i++) {sum[i] = Math.min(sum[i-2] + cost[i-2], sum[i-1] + cost[i-1]); // 递推公式}return sum[len];

因为我们要记录索引 i，用来取 cost 数组的值，所以无法优化空间复杂度。

最长公共子序列

Leetcode
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。
一个字符串的“子序列”是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的“公共子序列”是这两个字符串所共同拥有的子序列。

这是一道经典的动态规划题，基本上每本算法书中讲到动态规划时都会提到本题吧。这道题的初始状态是什么？如果给你两个长度为1的字符串，显然你一眼就能看出来，要么最长公共子序列不存在，要么就是最长公共子序列就是这个相等的字符串。
由此我们可以得出初始状态：如果两个字符串的长度都为1，或者我们只遍历到了两个字符串的第一个字符时，最长公共子序列的长度为0或者1。由此，我们也就能设置出一个二维数组dp[][]，其两个维度的长度分别为两个字符串的长度。
接下来，我们看看递推条件是什么：当递推到第一个字符串 s 的第 i 位、第二个字符串 t 的第 j 位 dp[i][j]，有两种可能：

1. s[i] == t[j] => 两个字符串的当前位相同了，我们可以将两个字符串各往前退一位，得到 dp[i-1][j-1]，显然 dp[i][j] = dp[i-1][j-1] + 1
2. s[i] != t[j] => 当前位置不相同，那么我们只能说对于其中一个字符串，删掉当前位置，看看最长公共子序列长度是多少。先将字符串 s 向前退一位，看看 dp[i-1][j]是多少；另外也看一下dp[i][j-1]是多少。取二者之大者，得到dp[i][j] = max{dp[i-1][j], dp[i][j-1]}

但是要注意一种特殊情况：如果只有一个字符串 s 长度为1，另一个字符串 t 长度大于1，此时数组 dp 的第一维长度也是1，dp[i-1]必然越界。所以，这也是一种特殊情况，大家自行想一下递推条件是什么，另外也考虑一下 dp 的第二维长度是1的情况。

综上所述，我们得到代码：

public int longestCommonSubsequence(String text1, String text2) {char[] cs1 = text1.toCharArray();char[] cs2 = text2.toCharArray();int len1 = cs1.length;int len2 = cs2.length;int[][] dp = new int[len1][len2];dp[0][0] = cs1[0] == cs2[0] ? 1 : 0; // 初始状态for (int i = 1;i < len1;i++) {dp[i][0] = cs1[i] == cs2[0] ? 1 : dp[i-1][0]; // 特殊递推公式}for (int j = 1;j < len2;j++) {dp[0][j] = cs1[0] == cs2[j] ? 1 : dp[0][j-1]; // 特殊递推公式}for (int i = 1;i < len1;i++) {for (int j = 1;j < len2;j++) {dp[i][j] = cs1[i] == cs2[j] ? dp[i-1][j-1]+1 : Math.max(dp[i-1][j], dp[i][j-1]); // 递推公式}}return dp[len1-1][len2-1];
}

因为我们要记录索引 i 和 j，用来获取字符串对应的字符，所以无法优化空间复杂度。

我们画一个二维表格，来看看整个递推的过程是怎么样的，假设两个字符串分别是"abcde"和"ace"：

	t=	a	c	e
s=	index	0	1	2
a	0	1	1	1
b	1	1	1	1
c	2	1	2	2
d	3	1	2	2
e	4	1	2	3

大家可以自己再多举几个例子，多画些图，从中体会到递推、动态规划的思路。

矩阵

接下来是几道矩阵相关的题目，可想而知我们会用到二维数组，大家注意观察这里的二维数组是否能降维到一维。

矩阵路线总数

牛客网
Leetcode
一个机器人位于一个 m x n 矩阵的左上角，机器人每次只能向下或者向右移动一步，请问达到矩阵的右下角总共有多少条不同的路径？

经过了上述题目，尤其是跳台阶那道题的考验，相信大家解这道题应该毫无难度了吧？初始状况、极值、递推公式都挺容易想出来的，代码如下：

public int uniquePaths(int m, int n) {if (m == 1 || n == 1) {return 1;}int[][] dp = new int[m][n];for (int i = 0;i < m;i++) {dp[i][0] = 1;}for (int j = 1;j < n;j++) {dp[0][j] = 1;}for (int i = 1;i < m;i++) {for (int j = 1;j < n;j++) {dp[i][j] = dp[i-1][j] + dp[i][j-1]; // 递推条件和跳台阶很像}}return dp[m-1][n-1];
}

既然这道题和跳台阶很像，那么这道题可不可以降低数组维度呢？答案是可以的。譬如我们将 dp[m][n] 降维到 dp[n]，那么我们可以看到原来的 dp[i][j] 和 dp[i-1][j] 可以由现在的 dp[j] 来表示，只不过 dp[i-1][j] 代表前一时刻的 dp[j]，而 dp[i][j] 代表当前时刻的 dp[j]，可以用类似跳台阶题目中辗转腾挪的方法来实现，代码如下：

public int uniquePaths(int m, int n) {if (m == 1 || n == 1) {return 1;}int[] dp = new int[n];for (int i = 0;i < n;i++) {dp[i] = 1;}for (int i = 1;i < m;i++) {for (int j = 1;j < n;j++) {dp[j] = dp[j] + dp[j-1];}}return dp[n-1];
}

空间复杂度由O(m*n)降为O(n)。

另外值得一提的是，如果有数学非常好的朋友，可以试一下用数学中的“组合”来解这道题，效率非常高，但是难度也是MAX。

矩阵路线总数+有障碍物

Leetcode
在上一题的基础上，还给出一个网格矩阵int[m][n] obstacleGrid，若obstacleGrid[i][j] == 1，说明这一格有障碍物，不能通行；否则obstacleGrid[i][j] == 0，可以通行。这种情况下从左上角走到右下角的路线总数是多少？

这种情况下，我们稍微修改一下递推公式，先写出二维数组的代码：

public int uniquePathsWithObstacles(int[][] obstacleGrid) {if (obstacleGrid[0][0] == 1) {return 0;}int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][n];dp[0][0] = 1;for (int i = 1;i < m;i++) {if (dp[i-1][0] == 0 || obstacleGrid[i][0] == 1) { // 如果前一个 dp[i-1][0] 等于0，说明这一列的前几行已经出现了障碍物，后续的 dp[i][0] 都会为0dp[i][0] = 0;}else {dp[i][0] = 1;}}for (int j = 1;j < n;j++) {if (dp[0][j-1] == 0 || obstacleGrid[0][j] == 1) {dp[0][j] = 0;}else {dp[0][j] = 1;}}for (int i = 1;i < m;i++) {for (int j = 1;j < n;j++) {dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : (dp[i-1][j] + dp[i][j-1]);}}return dp[m-1][n-1];
}

显然这种最简单、最经典的解法，额外空间复杂度为O(m*n)。接下来如何降为O(n)，留给大家自己思考。这里我们还可以获得一种额外空间复杂度为O(1)的方法，就是不创建 dp 数组了，直接复用 obstacleGrid 数组！感谢 obstacleGrid 和 dp 在两个维度上的长度都一样，而且obstacleGrid[i][j] 只用在 dp[i][j] 的计算中，计算完就没用了。这种取巧的方式并不会适用于太多动态规划题目。

矩阵的最小路径和

牛客网
Leetcode
给定一个包含非负整数的 m x n 矩阵 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。每次只能向下或者向右移动一步。

这道题和矩阵路线总数的关系，就相当于跳台阶和最小花费跳台阶的关系，每一格/每一台阶是加了权重的。或者说，这道题是最小花费跳台阶的二维数组版。巧合的是，这道题也可以复用 grid 数组，使得额外空间复杂度降为O(1)。我们直接写出复用数组的代码：

public int minPathSum(int[][] grid) {int m = grid.length;int n = grid[0].length;for (int i = 1;i < m;i++) {grid[i][0] = grid[i-1][0] + grid[i][0];}for (int j = 1;j < n;j++) {grid[0][j] = grid[0][j-1] + grid[0][j];}for (int i = 1;i < m;i++) {for (int j = 1;j < n;j++) {grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);}}return grid[m-1][n-1];
}

三角形的最小路径和

Leetcode
给定一个二维数组 triangle 来模拟一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是 下标与上一层结点下标相同 或者 下标等于上一层结点下标+1 的两个结点。也就是说，如果正位于当前行的下标 i，那么下一步可以移动到下一行的下标 i 或 i+1 。
规定：triangle[0].length == 1， 且 triangle[i].length == triangle[i - 1].length + 1，所以它刚好是个等腰直角三角形。triangel 的一个例子是 triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]，画成图就是
2
3 4
6 5 7
4 1 8 3
这样大家能更直观地看出来如何求出最短路径。初始状态、极值和递推公式相信大家也都已经可以自行推理出来了，参考的代码如下：

public int minimumTotal(List<List<Integer>> triangle) {int m = triangel.size();int[][] dp = new int[m][n];dp[0][0] = triangel.get(0).get(0);for (int i = 1;i < m;i++) {List<Integer> list = triangel.get(i); // 因为 list 会被用到多次，所以我更偏向于先取得 listdp[i][0] = dp[i-1][0] + list.get(0);for (int j = 1;j < i;j++) {dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + list.get(j);}dp[i][i] = dp[i-1][i-1] + list.get(i);}return dp[m][m]
}

相信有些朋友已经发现了，这道题还是可以复用 triangle 链表的。不过由于链表操作比较复杂也比较耗时，其实我并不推荐这道题来复用，老老实实新建一个 dp 数组吧。也不能缩减维度了，所以写成上面这样就可以了。

接下来我们将告别easy题，来看middle题！

买卖股票的最佳时机（T+1天 / 当日不可卖）

Leetcode
给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

这道题与贪心算法博客中的“买卖股票的最佳时机（T+0天 / 当日可卖）”这道题的区别是，买入当天是不能卖出的。还记得我们贪心算法的买股票时机吗？如果某一天的股票价格比前一天的低，那么就会卖掉前一天的并买入当天的。可是，前一天可能正好也是刚刚买入的（比如前前一天也比前一天高，所以前一天买入了），按照本题给定的规则，前一天较高位买入的反而不是一个好时机。
这道题其实并不需要使用动态规划来做，甚至Leetcode给出的官方题解也没有动态规划，而是用了模拟一次遍历的方式，记录遍历过程中遇到过的最小值，并用当前价格减去遇到过的最小值，不断获得当日卖出的最大利润。大家有空了可以尝试一下这种解法。

不过，我仍然认为这道题是一个不错的动态规划例题。给大家一个提示，这道动态规划解法中的极值，我设置为动态规划数组 dp，且设置 dp[i] 表示第 i 天必定卖出股票获得的利润，或者如果第 i 天卖出一定是亏损的那么就不进行任何买卖、dp[i] = 0。大家想想初始状态和递推公式应该是什么。又由于题目规定的是哪天卖出都可以，所以我们还要设置一个额外的变量 max，用来记录 dp[i] 中的最大值。

public int maxProfit(int[] prices) {int len = prices.length;if (len <= 1) {return 0;}int[] dp = new int[len];dp[0] = 0; // 初始状态：第0天是不能卖出的，所以 dp[0] = 0int max = 0;for (int i = 0;i < len;i++) {dp[i] = Math.max(dp[i-1] + prices[i] - prices[i-1], 0); // 递推公式：第 i 天卖了股票，可以看做前一天没有卖，拖到了今天卖。我们既然已知前一天卖掉的最大利润是 dp[i-1]，自然很容易得到递推公式max = Math.max(max, dp[i]); // max 不断记录 dp 数组中的最大值}return max;
}

不知道大家有没有意识到刚才的动态规划过程可以缩减 dp 数组的维度，使得额外空间复杂度为O(1)。大家自行尝试。

打家劫舍

牛客网
Leetcode
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组 nums，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

这也是一道经典的动态规划题目。设置一个动态规划数组 dp，dp[i] 表示前 i 间房屋能偷到的最高金额。两种特殊情况很明显：（1）如果只有一个房屋，那么就会偷这个房屋，dp[0] = nums[0]；（2）如果只有两个房屋，考虑一下哪家更值钱，dp[1] = max{nums[0], nums[1]}。
我们已经设置了极值，也得到了初始状况，接下来递推公式稍加思考也就能得到：dp[i] = max{dp[i-2] + nums[i], dp[i-1]}（前者表示第 i 家进行偷窃所能产生的最高金额，后者表示第 i 家不进行偷窃所能产生的最高金额）。代码如下：

public int rob(int[] nums) {int len = nums.length;if (len < 1) {return nums[0];}int[] dp = new int[len];dp[0] = nums[0];dp[1] = Math.max(nums[0], nums[1]);for (int i = 0;i < len;i++) {dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);}return dp[len-1];
}

另外，这里我们可以用a, b, c三个变量来代替dp[i-2], dp[i-1]和dp[i]，缩减数组维度，大家自行尝试。

可以对打家劫舍的题目做一点小改动，形成首尾房屋相连/房屋围成圈的打家劫舍（牛客网
Leetcode）。改动的点在于，第一个房屋和最后一个房屋也有相连的警报系统，或者说房屋是围成圈的、首尾相连，这时候怎么做呢？
其实说起来解法也很简单。还是刚才的动态规划算法，只不过计算两次，一次计算只偷 (0, n-1) 的，另一次只偷 (1, n)的，二者取其大者即可。

编辑距离

牛客网
Leetcode
给你两个单词 word1 和 word2，且你可以对单词 word1 进行三种操作：插入一个字符、删除一个字符或替换一个字符。请返回将 word1 转换成 word2 所使用的最少操作数。
这道题有点类似于“最长公共子序列”。给大家一个例子，word1 = “horse”, word2 = “ros”，大家画一个“最长公共子序列”中画的图，会对如何用动态规划解这道题有帮助。我把这个图贴在了代码后面，大家可以一起看一下。

画完图的同学应该很明晰如何进行动态规划了。首先对于动态规划数组 dp，我们规定 dp[i][j] 表示 子字符串word1[0-i] 要编辑成为 子字符串 words[0-j] 的操作次数。那么显然，dp[0][0] = 0（如果word1[0] == word2[0]）或 1（如果word1[0] != word2[0]）；dp[0][j] = dp[0][j-1]（如果word1[0] == word2[0]）或 dp[0][j-1]+1（如果word1[0] != word2[0]）；dp[i][0] 同理；而最复杂的 dp[i][j]，在word1[0] != word2[0]的时候，是等于 dp[i-1][j-1] 的，否则是取 dp[i-1][j-1], dp[i-1][j], dp[i][j-1] 三者的最小值并加1。
代码如下：

public int minDistance(String word1, String word2) {char[] cs1 = word1.toCharArray();char[] cs2 = word2.toCharArray();int len1 = cs1.length;int len2 = cs2.length;int[][] dp = new int[len1][len2];dp[0][0] = cs1[0] == cs2[0] ? 0 : 1;for (int i = 1;i < len1;i++) {dp[i][0] = (cs1[i] == cs2[0] ? 0 : 1) + dp[i-1][0];}for (int j = 1;j < len2;j++) {dp[0][j] = (cs1[0] == cs2[j] ? 0 : 1) + dp[0][j-1];}for (int i = 1;i < len1;i++) {for (int j = 1;j < len2;j++) {dp[i][j] = cs1[i] == cs2[j] ? dp[i-1][j-1] : (Math.min(Math.min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1])+1);}}return dp[len1-1][len2-1];
}

这个数组就无法缩减了维度了，代码的额外空间复杂度为O(m*n)。

刚才给的例子我们画个图，是这样的：

	word2=	r	o	s
word1=	index	0	1	2
h	0	1	2	3
o	1	2	1	2
r	2	2	2	2
s	3	3	3	2
e	4	4	4	3

经过前面的几道例题的挑战，相信大家已经熟练掌握如何用动态规划解题了。接下来让我们来看三道hard的动态规划题目，看看它们为什么称得上是hard难度的。

数字解码成字符

牛客网
Leetcode
一条包含字母 A-Z 的消息通过以下映射进行了编码 ：
“1” -> ‘A’
“2” -> ‘B’
…
“25” -> ‘Y’
“26” -> ‘Z’
然而，在 解码 已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（“2” 和 “5” 与 “25”）。
例如，“11106” 可以映射为：
“AAJF” ，将消息分组为 (1, 1, 10, 6)
“KJF” ，将消息分组为 (11, 10, 6)
消息不能分组为 (1, 11, 06) ，因为 “06” 不是一个合法编码（只有 “6” 是合法的）。
注意，可能存在无法解码的字符串。
给你一个只含数字的非空字符串 s ，请计算并返回解码方法的总数。如果没有合法的方式解码整个字符串，返回 0。

大家自己先分析一下如何用动态规划解题，应该能发现其实这道题跟“跳台阶”挺像的吧。显然我们设置一个数组 dp，dp[i] 表示s(0,i)解码成字符的方法总数。那么初始状态 dp[0] 和 dp[1] 挺好定义的，递推公式有两种，形成两位数=>字符的情况下，有 dp[i] = dp[i-1] + dp[i-2]，否则这个递推公式是 dp[i] = dp[i-1] 也挺明确的。大家兴高采烈地写下整体代码后，才发现会有坑。
坑在哪里呢？就是’0’这个字符，不能单独被解码，也不能作为字符串的前导字符被解码。如此一来，比如字符串“404”根本无法被解码，“106”的解码可能性也只有1种。所以我们在确定初始状态和递推的过程中，一定要排除0的影响，甚至遇到’0’且它不能和前一个字符匹配成“10”或“20”的情况下，直接可以让函数停止并返回0.
代码如下：

public int numDecodings(String s) {char[] cs = s.toCharArray();int len = cs.length;int[] dp = new int[len];if (cs[0] == '0') { // 注意 cs[0] == 0 的情况return 0;}dp[0] = 1;if (len == 1) {return dp[0];}if (cs[0] == '1' || cs[0] == '2' && cs[1] <= '6') {dp[1] = cs[1] == '0' ? 1 : 2; // 注意 cs[1] == 0 的情况}else if (cs[1] == '0') { // 注意 cs[1] == 0 的情况return 0;}else {dp[1] = 1;}for (int i = 2;i < len;i++) {if (cs[i-1] == '1' || cs[i-1] == '2' && cs[i] <= '6') {dp[i] = (cs[i] == '0' ? 0 : dp[i-1]) + dp[i-2]; // 注意 cs[i] == 0 的情况}else if (cs[i] == '0') {return 0; // 注意 cs[i] == 0 的情况}else {dp[i] = dp[i-1];}}return dp[len-1];
}

本题可以使用三个变量 a, b, c 来代替数组缩减额外空间复杂度，感兴趣的朋友们可以试试。

最长回文子串

牛客网
Leetcode
给你一个字符串 s，找到 s 中最长的回文子串。
这里我们要指出，“子串”必须是字符串中截取出来的一段，它的范围比“子序列”要小。比如对于字符串“abcde”，字符串“ace”是它的子序列，但不是子串。
“回文”的意思大家应该也都理解，比如字符串“abba”，“aba”，“a”都是回文字符串，而“ab”则不是。
这道题是用动态规划来解的，但是动态规划只体现在我们思考的过程中，并不需要在代码中展现。我们设定动态规划数组 dp[n][n]，其中 n 为字符串 s 的长度，且数组 dp 的每个元素是布尔类型的。设定 dp[i][j] 代表字符串 s 的子串 s(i,j) 是否为回文串，其中 i <= j。
那么初始状态是什么呢？我们能知道的初始的必定是回文子串的，只有s(i,i)这个只包含一个字符的子串，所以设定 dp[i][i] = true；另外，对于长度为2的子串，如果 s[i] == s[i+1]，那么 dp[i][i+1] = true，否则 dp[i][i+1] = false。
接下来，我们可以着手去找回文子串了。递推公式为，dp[i-1][j+1] = dp[i][j] & s[i-1] == s[j+1]。这个也是好理解的，只有当一个字符串的最左和最右字符相同，且除去这两个字符的内部子串也是回文串时，它本身才是一个回文串。
具体遍历是，对于长度为奇数的子串，它的最中间有一个不需要和别的字符相比较的字符，我们就从这个字符 s[i] 入手，对应设定的 dp[i][i] = true 的情况；对于长度为偶数的子串，它的最中间有两个相邻的需要比较的字符，对应设定的 dp[i][i+1] = true or false的情况。

不过在代码中，可以不具体实现这个 dp 数组。我们来看代码是怎么样做到的：

public String longestPalindrome(String s) {if (s == null || s.length() < 1) {return "";}int[] longestIndex = new int[2];char[] cs = s.toCharArray();int len = cs.length;for (int i = 0;i < len;i++) {expand(cs, i, i, longestIndex); // 由s(i,i)扩展出来的最长回文子串的左右下标expand(cs, i, i+1, longestIndex); // 由s(i,i+1)扩展出来的最长回文子串的左右下标}return s.substring(longestIndex[0], longestIndex[1]+1); // 注意 substring() 的用法，longestIndex[1]需要加1才能把longestIndex[1]位的字符截进去
}// 如果当前的极长回文子串长度大于已经记录下来的最长回文子串长度，则替换
private void expand(char[] cs, int left, int right, int[] longestIndex) {while (left >= 0 && right < cs.length && cs[left] == cs[right]) {left--;right++;}if ((right-1)- (left+1) + 1 > longestIndex[1] - longestIndex[0] + 1) {longestIndex[0] = left + 1;longestIndex[1] = right - 1;}
}

地下城游戏

Leetcode
恶魔们抓住了公主并将她关在了地下城 dungeon 的右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快解救公主，骑士决定每次只向右或向下移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。

相信大家看到这道题可能会觉得这有啥难度嘛，不就是“矩阵最短路径”的一个小小变体嘛！那么好，大家尝试着写一下代码，然后我给出一个例子：

0	-2	3
-1	0	0

从左上角(0,0)开始走到右下角(1,2)，如果按照“矩阵最短路径”的解法，我们会走(0,0)->(0,1)->(0,2)->(1,2)的路径，因为这样骑士救出公主时，还能比出发时多1点体力。
按照这样的路径的话，骑士在出发时需要的最低初始体力值是3，才能击败(0,1)处的恶魔。可是，我如果走(0,0)->(1,0)->(1,1)->(1,2)的路径，只需要最低初始体力值是2，击败了(1,0)的恶魔就可以了！

发现没有，这道题和“矩阵最短路径”完全不一样，因为我们要设置的那个极值，应该是和初始体力值有关的，而和经过路径的消耗体力或者恢复体力值之和没有关系。
我们应该将极值定义为：动态规划数组 dp 中的 dp[i][j] 代表从 (i,j) 能够走到终点，所需要的最小初始体力值。
可能大家会奇怪，那么初始状态很难获得了。是啊，dp[0][0] 反而变成了我们题目要求的值。不过大家会发现，动态规划数组中有一个坐标的值很容易取得了，那就是 dp[m-1][n-1]。如果 dungeon[m-1][n-1] >= 0，那么 dp[m-1][n-1] 只需要是 1；否则的话，dp[m-1][n-1] 就应该是
-dungenon[m-1][n-1] + 1。
很奇怪哦，平时我们都是已知 dp[0][0]，要求 dp[m-1][n-1]，今天却刚好倒过来了。那没关系，那我们就从 (m-1, n-1) 倒推回 (0,0)，递推公式不难大家就自行思考。代码如下：

public int calculateMinimumHP(int[][] dungeon) {int m = dungeon.length;int n = dungeon[0].length;int[][] dp = new int[m][n];dp[m-1][n-1] = Math.max(-dungeon[m-1][n-1] + 1, 1); // 初始状态for (int i = m-2;i >= 0;i--) {dp[i][n-1] = Math.max(-dungeon[i][n-1] + dp[i+1][n-1], 1); // 最后一列}for (int j = n-2;j >= 0;j--) {dp[m-1][j] = Math.max(-dungeon[m-1][j] + dp[m-1][j+1], 1); // 最后一行}for (int i = m-2;i >= 0;i--) {for (int j = n-2;j >= 0;j--) {dp[i][j] = Math.max(-dungeon[i][j] + Math.min(dp[i+1][j], dp[i][j+1]), 1);}}return dp[0][0];			
}

当然，这里还是可以复用 dungeon 数组的，感兴趣的朋友们可以自行尝试。
给大家一个例子：

-2	-3	3
-5	10	1
10	30	-5

可以试试看 dp 数组是怎么递推出来的。

总结与心得

其实，当我们在面试中遇到动态规划题，一般是两种情况：要么是面试官很欣赏我们，想考验我们，那这时如果我们迅速写出题解，相信高薪不是梦了；否则或许是面试官想要劝退我们，想用代码题不通过来让我们死心，此时我们迅速写出题解，也能给我们留一线生机。所以，掌握动态规划的解法真的很重要！
现在，相信大家已经能很快看出一道题能否用动态规划了。而且，对于绝大多数的动态规划题目，相信大家也能快速找到初始状态并进行极值的设置，最后思考得到递推公式。记住这三步，动态规划就不再是困扰我们的大难题！如果还能想到缩减额外空间复杂度，肯定还能让面试官眼前一亮！
坚持，加油，胜利就在前方！