《算法系列》之动态规划
简介
面试官常考的类型很多，不同的面试官考查的题也不尽相同，但如果真有什么题是大多数面试官都喜欢的话，那就一定是动态规划，真正的算法题无冕之王。为什么这么说呢？因为他的变化性很大，题目规律也很难找到，甚至大多数时候，我们都不清楚，我们需要用动态规划去解决这个题。除非我们做过类似的题，否则我们并不能肯定的说，下一道动态规划我们一定会做。出现新题时，我们依然可能会束手无策。 再加上网上很多内容把本就复杂的东西，说的更复杂了。我们今天做一做减法，只需要记住一句话： 解题步骤 + 状态转移方程式 = 动态规划的答案。
理论基础
动态规划(英语：Dynamic programming，简称 DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果，因此动态规划方法所耗时间往往远少于朴素解法。
动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化递归，自底向上就是递推。使用动态规划解决的问题有个明显的特点，一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做无后效性，求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次，具有天然剪枝的功能，从而减少计算量。
解题步骤
动态规划并没有固定的解题答案， 每道题都是不同的状态转移方程式，但是我们可以总结出解题步骤，可以很大程度的解决动态规划的题难的问题。 解题步骤加状态转移方程式，即是所有动态规划题的模板。 一般解题步骤需要以下三步：
- 确定dp数组（dp table）以及下标的含义
动规里一定需要数组，作为每一次变化的存储介质，有时你可能只用到两个变量，其实也是发挥了数组的作用。而我们需要明确知道，数组的整体含义与每个下标的含义分别代表了什么，数组的整体含义即：我们存的是什么？下标的含义即：我们存的每一步存的值含义是什么。只有明白了这些，我们才不至于，做完题后，人还是迷的，下次做题也全靠感觉，感觉到了，题就解了，没到就写不出来。 - 确定递推公式，即确定状态转移方程式
状态转移方程式是解动规题的核心，我们不是说动规是把原问题分解成很多小步骤解决吗，那小步骤又是怎么变化的？或者说这每一步应该怎么走？其实就是这个状态转移方程式，就是描述每一步之间的一个变化关系，比如说从 i 到 i + 1 之间，它的一个变化函数，就是我们的状态转移方程式。 - 确定dp数组如何初始化与遍历方向
有时我们整个解题步骤中很容易忽略，dp 数组的初始化与遍历方向上的一些细节问题，但他们其实同样重要。比如初化时从 0 开始还是从 1 开始，含义是不同的，最后结果也是不同的。再比如遍历方向， 我们并不总是从左到右，有时涉及到二维数组，我们可能还要从上到下，从右到左。
其它
动态规划里还有难一点类型的题，即背包问题，我们可以学习下这位大牛的文章：背包九讲。其中重点可以放在01背包问题和完全背包问题上，之后有机会，会和大家分享一下相关内容。
解题心得
- 动态规划变化性很大，需要多加练习找出题感。
- 确定动态题的数组含义是解题关键之一。
- 状态转移方程式是动规题的核心，写出来可做到一击必杀。
- dp数组如何初始化与遍历方向同样重要，不容忽视。
- 动态规划并没有固定的解题模板，但是有统一的解题步骤， 解题步骤加状态转移方程式，即是所有动态规划题的模板。
- 动态规划与贪心算法的区别是：贪心没有状态推导，而是从局部直接选最优的，动规需要考虑全局信息。
- 背包问题可做为动规里的进阶类型题，学习时重点放在01背包问题和完全背包问题即可。
算法题目
5. 最长回文子串
题目解析：按动态规划步骤解题即可。
代码如下：
/**
* 动态规划
*/
class Solution {
public static String longestPalindrome(String s) {
// 边界条件判断
if (s.length() < 2)
return s;
// start表示最长回文串开始的位置，
// maxLen表示最长回文串的长度
int start = 0, maxLen = 1;
int length = s.length();
boolean[][] dp = new boolean[length][length];
for (int right = 1; right < length; right++) {
for (int left = 0; left < right; left++) {
// 如果两种字符不相同，肯定不能构成回文子串
if (s.charAt(left) != s.charAt(right))
continue;
// 下面是s.charAt(left)和s.charAt(right)两个
// 字符相同情况下的判断
// 如果只有一个字符，肯定是回文子串
if (right == left) {
dp[left][right] = true;
} else if (right - left <= 2) {
// 类似于"aa"和"aba"，也是回文子串
dp[left][right] = true;
} else {
// 类似于"a******a"，要判断他是否是回文子串，只需要
// 判断"******"是否是回文子串即可
dp[left][right] = dp[left + 1][right - 1];
}
// 如果字符串从left到right是回文子串，只需要保存最长的即可
if (dp[left][right] && right - left + 1 > maxLen) {
maxLen = right - left + 1;
start = left;
}
}
}
// 截取最长的回文子串
return s.substring(start, start + maxLen);
}
}
10. 正则表达式匹配
题目解析：按动态规划步骤解题即可。
代码如下：
/**
* 动态规划
*/
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] f = new boolean[m + 1][n + 1];
f[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p.charAt(j - 1) == '*') {
f[i][j] = f[i][j - 2];
if (matches(s, p, i, j - 1)) {
f[i][j] = f[i][j] || f[i - 1][j];
}
} else {
if (matches(s, p, i, j)) {
f[i][j] = f[i - 1][j - 1];
}
}
}
}
return f[m][n];
}
public boolean matches(String s, String p, int i, int j) {
if (i == 0) {
return false;
}
if (p.charAt(j - 1) == '.') {
return true;
}
return s.charAt(i - 1) == p.charAt(j - 1);
}
}
42. 接雨水
题目解析：按动态规划步骤解题即可。
代码如下：
/**
* 动态规划
*/
class Solution {
public int trap(int[] height) {
int n = height.length;
if (n == 0) {
return 0;
}
int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; ++i) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
}
44. 通配符匹配
题目解析：按动态规划步骤解题即可。
代码如下：
/**
* 动态规划
*/
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 1; i <= n; ++i) {
if (p.charAt(i - 1) == '*') {
dp[0][i] = true;
} else {
break;
}
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
} else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
}
53. 最大子数组和
题目解析：找出以当前数为右边界的最大数，再从其中找去最大者。
代码如下：
/**
* 动态规划
*/
class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
int max = nums[0];
// 找出以当前数为右边界的最大数max，再从中找出res
for (int i = 1; i < nums.length; i++) {
if (max >= 0) {
max += nums[i];
} else {
max = nums[i];
}
res = Math.max(res, max);
}
return res;
}
}
62. 不同路径
题目解析：按动态规划步骤解题，其中要做缓存，不用每次都计算，用空间换时间。
代码如下：
/**
* 动态规划
*/
class Solution {
public int uniquePaths(int m, int n) {
// 申请内存用于缓存子路径结果，不用每次都计算，提高算法效率
int[][] nums = new int[m][n];
return helper(nums, m - 1, n - 1);
}
public int helper(int[][] nums, int row, int column) {
int res = 0;
// 递归出口
if (row == 0 && column == 0) {
res = 1;
}
if (row > 0 && column == 0) {
// 判断是否在缓存中
if (nums[row - 1][column] != 0) {
res = nums[row - 1][column];
} else {
res = helper(nums, row - 1, column);
// 将结果缓存
nums[row][column] = res;
}
}
if (row == 0 && column > 0) {
// 判断是否在缓存中
if (nums[row][column - 1] != 0) {
res = nums[row][column - 1];
} else {
res = helper(nums, row, column - 1);
// 将结果缓存
nums[row][column] = res;
}
}
if (row > 0 && column > 0) {
// 判断是否在缓存中
if (nums[row - 1][column] != 0 && nums[row][column - 1] != 0) {
res = nums[row - 1][column] + nums[row][column - 1];
} else {
res = helper(nums, row - 1, column) + helper(nums, row, column - 1);
// 将结果缓存
nums[row][column] = res;
}
}
return res;
}
}
63. 不同路径 II
题目解析：按动态规划步骤解题即可，此类题，求所有路径一般就是用回溯，求所有个数一般就是用动规，一个二维数组就能搞定。
代码如下：
/**
* 动态规划
*/
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int row = obstacleGrid.length;
int column = obstacleGrid[0].length;
// 记录所有数量的数组
int[][] nums = new int[row][column];
nums[0][0] = 1;
// 对二维数组做操作
for (int r = 0; r < row; r++) {
for (int c = 0; c < column; c++) {
if (obstacleGrid[r][c] == 1) {
nums[r][c] = 0;
} else if (r > 0 && c > 0) {
nums[r][c] = nums[r - 1][c] + nums[r][c - 1];
} else if (r > 0) {
nums[r][c] = nums[r - 1][c];
} else if (c > 0) {
nums[r][c] = nums[r][c - 1];
}
}
}
return nums[row - 1][column - 1];
}
}
64. 最小路径和
题目解析：按动态规划步骤解题即可，状态转移方程式为：f(x,y) = min(f(x-1,y) + a[i], f(x,y-1) + a[i])。
代码如下：
/**
* 动态规划
*/
class Solution {
public int minPathSum(int[][] grid) {
int row = grid.length;
int column = grid[0].length;
// 申请一个结果缓存空间，缓存结果，避免重复计算
int[][] map = new int[row][column];
int res = helper(grid, map, row - 1, column - 1);
return res;
}
public int helper(int[][] grid, int[][] map, int x, int y) {
int sum = 0;
if (x == 0 && y == 0) {
return grid[0][0];
}
if (x > 0 && y > 0) {
// 如果缓存里有，直接获取
if (map[x][y] != 0) {
sum = map[x][y];
} else {
// 多种情况下，选择小的路径
sum = Math.min(helper(grid, map, x - 1, y) + grid[x][y], helper(grid, map, x, y - 1) + grid[x][y]);
map[x][y] = sum;
}
}
if (x > 0 && y == 0) {
// 如果缓存里有，直接获取
if (map[x][y] != 0) {
sum = map[x][y];
} else {
sum = helper(grid, map, x - 1, y) + grid[x][y];
map[x][y] = sum;
}
}
if (x == 0 && y > 0) {
// 如果缓存里有，直接获取
if (map[x][y] != 0) {
sum = map[x][y];
} else {
sum = helper(grid, map, x, y - 1) + grid[x][y];
map[x][y] = sum;
}
}
return sum;
}
}
70. 爬楼梯
题目解析：按动态规划步骤解题即可，状态转移方程式为：f(n) = f(n-1) + f(n-2)。
代码如下：
/**
* 动态规划
*/
class Solution {
public int climbStairs(int n) {
// 申请内存，用以缓存分支结果，不用每次都计算该值，提升运行效率
int[] nums = new int[46];
return helper(nums, n);
}
public int helper(int[] nums, int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
int n1 = 0;
int n2 = 0;
// 曾计算过该值，则直接使用
if (nums[n - 1] != 0) {
n1 = nums[n - 1];
} else {
n1 = helper(nums,n - 1);
nums[n - 1] = n1;
}
// 曾计算过该值，则直接使用即可
if (nums[n - 2] != 0) {
n2 = nums[n - 2];
} else {
n2 = helper(nums, n - 2);
nums[n - 2] = n2;
}
return n1 + n2;
}
}
72. 编辑距离
题目解析：按动态规划步骤解题即可。
代码如下：
/**
* 动态规划
*/
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
// 初始化
for (int i = 1; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 1; j <= n; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 因为dp数组有效位从1开始
// 所以当前遍历到的字符串的位置为i-1 | j-1
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
}
}
}
return dp[m][n];
}
}
87. 扰乱字符串
题目解析：按动态规划步骤解题即可。
代码如下：
/**
* 动态规划
*/
class Solution {
// 记忆化搜索存储状态的数组
// -1 表示 false，1 表示 true，0 表示未计算
int[][][] memo;
String s1, s2;
public boolean isScramble(String s1, String s2) {
int length = s1.length();
this.memo = new int[length][length][length + 1];
this.s1 = s1;
this.s2 = s2;
return dfs(0, 0, length);
}
// 第一个字符串从 i1 开始，第二个字符串从 i2 开始，子串的长度为 length，是否和谐
public boolean dfs(int i1, int i2, int length) {
if (memo[i1][i2][length] != 0) {
return memo[i1][i2][length] == 1;
}
// 判断两个子串是否相等
if (s1.substring(i1, i1 + length).equals(s2.substring(i2, i2 + length))) {
memo[i1][i2][length] = 1;
return true;
}
// 判断是否存在字符 c 在两个子串中出现的次数不同
if (!checkIfSimilar(i1, i2, length)) {
memo[i1][i2][length] = -1;
return false;
}
// 枚举分割位置
for (int i = 1; i < length; ++i) {
// 不交换的情况
if (dfs(i1, i2, i) && dfs(i1 + i, i2 + i, length - i)) {
memo[i1][i2][length] = 1;
return true;
}
// 交换的情况
if (dfs(i1, i2 + length - i, i) && dfs(i1 + i, i2, length - i)) {
memo[i1][i2][length] = 1;
return true;
}
}
memo[i1][i2][length] = -1;
return false;
}
public boolean checkIfSimilar(int i1, int i2, int length) {
Map<Character, Integer> freq = new HashMap<Character, Integer>();
for (int i = i1; i < i1 + length; ++i) {
char c = s1.charAt(i);
freq.put(c, freq.getOrDefault(c, 0) + 1);
}
for (int i = i2; i < i2 + length; ++i) {
char c = s2.charAt(i);
freq.put(c, freq.getOrDefault(c, 0) - 1);
}
for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
int value = entry.getValue();
if (value != 0) {
return false;
}
}
return true;
}
}
91. 解码方法
题目解析：走楼梯加强版，按动态规划步骤解题即可，当前数字是0：dp[i] = dp[i-2]。当前数字不是0：dp[i] = dp[i-1];
代码如下：
/**
* 动态规划
*/
class Solution {
public int numDecodings(String s) {
final int length = s.length();
if(length == 0) return 0;
if(s.charAt(0) == '0') return 0;
int[] dp = new int[length+1];
dp[0] = 1;
for(int i=0;i<length;i++){
dp[i+1] = s.charAt(i)=='0'?0:dp[i];
if(i > 0 && (s.charAt(i-1) == '1' || (s.charAt(i-1) == '2' && s.charAt(i) <= '6'))){
dp[i+1] += dp[i-1];
}
}
return dp[length];
}
}
96. 不同的二叉搜索树
题目解析：按动态规划步骤解题即可，状态转移方程式为：G(n) = G(0)G(n-1)+G(1)(n-2)+…+G(n-1)*G(0)。
代码如下：
/**
* 动态规划
*/
class Solution {
public int numTrees(int n) {
if(n <= 2) return n;
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
// 外层的循环为了填充这个dp数组
for(int i = 3; i <=n ; i++ ){
// 内层循环用来遍历各个元素用作根的情况
for(int j = 1; j <= i; j++){
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}
97. 交错字符串
题目解析：按动态规划步骤解题即可。
代码如下：
/**
* 动态规划
*/
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int s1len = s1.length();
int s2len = s2.length();
int s3len = s3.length();
if (s1len + s2len != s3len) return false;
boolean[][] dp = new boolean[s1len + 1][s2len + 1];
dp[0][0] = true;
for (int i = 1; i <= s1len && (dp[i-1][0] && s1.charAt(i-1) == s3.charAt(i-1) ); i++) dp[i][0] = true;
for (int i = 1; i <= s2len && (dp[0][i-1] && s2.charAt(i-1) == s3.charAt(i-1)); i++) dp[0][i] = true;
for (int i = 1; i <= s1.length(); i++) { //s1
for (int j = 1; j <= s2.length(); j++) { //s2
dp[i][j] = (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i + j - 1))
|| (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i + j -1));
}
}
return dp[s1len][s2len];
}
}
115. 不同的子序列
题目解析：按动态规划步骤解题即可。
代码如下：
/**
* 动态规划
*/
class Solution {
public int numDistinct(String s, String t) {
// 以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
int[][] dp = new int[s.length() + 1][t.length() + 1];
// 初始化
for (int i = 0; i < s.length() + 1; i++) {
dp[i][0] = 1;
}
for (int i = 1; i < s.length() + 1; i++) {
for (int j = 1; j < t.length() + 1; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}else{
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[s.length()][t.length()];
}
}
118. 杨辉三角
题目解析：按动态规划步骤解题即可。
代码如下：
/**
* 动态规划
*/
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<>();
for (int i = 1; i <= numRows; i++) {
// 每一行的结果
List<Integer> list = new ArrayList<>();
for (int j = 1; j <= i; j++) {
// 第一列和最后一列为1
if (j == 1 || j == i) {
list.add(1);
} else {
list.add(res.get(i - 2).get(j - 2) + res.get(i - 2).get(j - 1));
}
}
res.add(list);
}
return res;
}
}
119. 杨辉三角 II
题目解析：按动态规划步骤解题即可。
代码如下：
/**
* 动态规划
*/
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> res = new ArrayList<>(rowIndex + 1);
long cur = 1;
for (int i = 0; i <= rowIndex; i++) {
res.add((int) cur);
cur = cur * (rowIndex - i) / (i + 1);
}
return res;
}
}
120. 三角形最小路径和
题目解析：按动态规划步骤解题即可，状态转移方程式：dp[j] = Math.min(dp[j],dp[j+1]) + curTr.get(j);。
代码如下：
/**
* 动态规划
*/
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0){
return 0;
}
// 滚动记录每一层的最小值
int[] dp = new int[triangle.size()+1];
for (int i = triangle.size() - 1; i >= 0; i--) {
List<Integer> curTr = triangle.get(i);
for (int j = 0; j < curTr.size(); j++) {
// 这里的dp[j] 使用的时候默认是上一层的，赋值之后变成当前层
dp[j] = Math.min(dp[j],dp[j+1]) + curTr.get(j);
}
}
return dp[0];
}
}
121. 买卖股票的最佳时机
题目解析：按动态规划步骤解题即可， 状态转移方程式为：前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}。
代码如下：
/**
* 动态规划
*/
class Solution {
public int maxProfit(int[] prices) {
if (prices.length <= 1) {
return 0;
}
int min = prices[0], max = 0;
for (int i = 1; i < prices.length; i++) {
// 状态转移方程式
max = Math.max(max, prices[i] - min);
// 更新最小值
min = Math.min(min, prices[i]);
}
return max;
}
}
122. 买卖股票的最佳时机 II
题目解析：按动态规划步骤解题即可。
代码如下：
/**
* 动态规划
*/
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < n; ++i) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[n - 1][0];
}
}
123. 买卖股票的最佳时机 III
题目解析：按动态规划步骤解题即可。
代码如下：
/**
* 动态规划
*/
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
// 边界判断, 题目中 length >= 1, 所以可省去
if (prices.length == 0) return 0;
// dp[i][j] 中i表示第i天，j为[0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金
int[][] dp = new int[len][5];
dp[0][1] = -prices[0];
// 初始化第二次买入的状态，是为了确保最后结果是最多两次买卖的最大利润
dp[0][3] = -prices[0];
for (int i = 1; i < len; i++) {
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
dp[i][2] = Math.max(dp[i - 1][2], dp[i][1] + prices[i]);
dp[i][3] = Math.max(dp[i - 1][3], dp[i][2] - prices[i]);
dp[i][4] = Math.max(dp[i - 1][4], dp[i][3] + prices[i]);
}
return dp[len - 1][4];
}
}
124. 二叉树中的最大路径和
题目解析：按动态规划步骤解题即可。
代码如下：
/**
* 动态规划
*/
class Solution {
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}
public int maxGain(TreeNode node) {
if (node == null) {
return 0;
}
// 递归计算左右子节点的最大贡献值
// 只有在最大贡献值大于 0 时，才会选取对应子节点
int leftGain = Math.max(maxGain(node.left), 0);
int rightGain = Math.max(maxGain(node.right), 0);
// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
int priceNewpath = node.val + leftGain + rightGain;
// 更新答案
maxSum = Math.max(maxSum, priceNewpath);
// 返回节点的最大贡献值
return node.val + Math.max(leftGain, rightGain);
}
}
132. 分割回文串 II
题目解析：按动态规划步骤解题即可。
代码如下：
/**
* 动态规划
*/
class Solution {
public int minCut(String s) {
int n = s.length();
boolean[][] g = new boolean[n][n];
for (int i = 0; i < n; ++i) {
Arrays.fill(g[i], true);
}
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
g[i][j] = s.charAt(i) == s.charAt(j) && g[i + 1][j - 1];
}
}
int[] f = new int[n];
Arrays.fill(f, Integer.MAX_VALUE);
for (int i = 0; i < n; ++i) {
if (g[0][i]) {
f[i] = 0;
} else {
for (int j = 0; j < i; ++j) {
if (g[j + 1][i]) {
f[i] = Math.min(f[i], f[j] + 1);
}
}
}
}
return f[n - 1];
}
}
139. 单词拆分
题目解析：按动态规划步骤解题即可，状态转移方程式为：if (wordDict.contains(s.substring(j,i)) && valid[j]) valid[i] = true;。
代码如下：
/**
* 动态规划
*/
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// 表示能否拆分为一个或多个在字典中出现的单词
boolean[] valid = new boolean[s.length() + 1];
valid[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (wordDict.contains(s.substring(j,i)) && valid[j]) {
valid[i] = true;
}
}
}
return valid[s.length()];
}
}
174. 地下城游戏
题目解析：按动态规划步骤解题即可。
代码如下：
/**
* 动态规划
*/
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int n = dungeon.length, m = dungeon[0].length;
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; ++i) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
dp[n][m - 1] = dp[n - 1][m] = 1;
for (int i = n - 1; i >= 0; --i) {
for (int j = m - 1; j >= 0; --j) {
int minn = Math.min(dp[i + 1][j], dp[i][j + 1]);
dp[i][j] = Math.max(minn - dungeon[i][j], 1);
}
}
return dp[0][0];
}
}
188. 买卖股票的最佳时机 IV
题目解析：按动态规划步骤解题即可。
代码如下：
/**
* 动态规划
*/
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices.length == 0) {
return 0;
}
int n = prices.length;
k = Math.min(k, n / 2);
int[][] buy = new int[n][k + 1];
int[][] sell = new int[n][k + 1];
buy[0][0] = -prices[0];
sell[0][0] = 0;
for (int i = 1; i <= k; ++i) {
buy[0][i] = sell[0][i] = Integer.MIN_VALUE / 2;
}
for (int i = 1; i < n; ++i) {
buy[i][0] = Math.max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
for (int j = 1; j <= k; ++j) {
buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);
}
}
return Arrays.stream(sell[n - 1]).max().getAsInt();
}
}
198. 打家劫舍
题目解析：按动态规划步骤解题即可，状态转移方程式：dp[i]=max(dp[i−2]+nums[i],dp[i−1])。
代码如下：
/**
* 动态规划
*/
class Solution {
public int rob(int[] nums) {
int length = nums.length;
if (nums == null || length == 0) {
return 0;
}
if (length == 1) {
return nums[0];
}
int[] dp = new int[length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[length - 1];
}
}
213. 打家劫舍 II
题目解析：按动态规划步骤解题即可，在原有基础上，考虑去掉首或尾的数组再次输入即可。
代码如下：
/**
* 动态规划
*/
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int len = nums.length;
if (len == 1)
return nums[0];
return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));
}
int robAction(int[] nums, int start, int end) {
int x = 0, y = 0, z = 0;
for (int i = start; i < end; i++) {
y = z;
z = Math.max(y, x + nums[i]);
x = y;
}
return z;
}
}
221. 最大正方形
题目解析：按动态规划步骤解题即可。
代码如下：
/**
* 动态规划
*/
class Solution {
public int maximalSquare(char[][] matrix) {
int m = matrix.length;
if(m < 1) return 0;
int n = matrix[0].length;
int max = 0;
// 表示以第i行第j列为右下角所能构成的最大正方形边长
int[][] dp = new int[m+1][n+1];
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) {
if(matrix[i-1][j-1] == '1') {
dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
max = Math.max(max, dp[i][j]);
}
}
}
return max * max;
}
}
264. 丑数 II
题目解析：按动态规划步骤解题即可，丑数一定由前面的丑数乘以2，或者乘以3，或者乘以5得来，用三个指针，从左往右，每次取最小的丑数为下一位即可。
代码如下：
/**
* 动态规划
*/
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
int p2 = 1, p3 = 1, p5 = 1;
for (int i = 2; i <= n; i++) {
int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
dp[i] = Math.min(Math.min(num2, num3), num5);
if (dp[i] == num2) {
p2++;
}
if (dp[i] == num3) {
p3++;
}
if (dp[i] == num5) {
p5++;
}
}
return dp[n];
}
}
279. 完全平方数
题目解析：按动态规划步骤解题即可。
代码如下：
/**
* 动态规划
*/
class Solution {
public int numSquares(int n) {
int max = Integer.MAX_VALUE;
// 和为i的完全平方数的最少数量为dp[i]
int[] dp = new int[n + 1];
// 初始化
for (int j = 0; j <= n; j++) {
dp[j] = max;
}
// 当和为0时，组合的个数为0
dp[0] = 0;
// 遍历物品
for (int i = 1; i * i <= n; i++) {
// 遍历背包
for (int j = i * i; j <= n; j++) {
if (dp[j - i * i] != max) {
dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
}
}
}
return dp[n];
}
}
300. 最长递增子序列
题目解析：按动态规划步骤解题即可，状态转移方程式为：dp[i] = max(dp[i], dp[j] + 1)。
代码如下：
/**
* 动态规划
*/
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int res = 0;
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
// 取最长的子序列
if(dp[i] > res) res = dp[i];
}
return res;
}
}
回到首页
刷 leetcode 500+ 题的一些感受
下一篇
《算法系列》之设计