动态规划刷题总结

动态规划算法描述

动态规划（dynamic programming）是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。

• dp[i]表示子问题的解
• 初始状态
• 状态转移方程
• 通过只保留必要的状态来节省空间，这种方法叫做滚动变量，或者滚动数组

经典问题：

• 爬楼梯
• 斐波那契队列

DP的问题特点

• 最优子结构：原问题的最优价，是由子问题的最优解得来的
• 无后效性：给定一个确定的状态，它的未来发展只与当前状态有关，而与过去经历的所有状态无关 。

解题思路：

• 判断是否是DP

  • 先观察问题是否适合使用回溯（穷举）解决 。适合用回溯解决的问题通常满足“决策树模型” ，这种问题可以使用树形结构来描述，其中每一个节点代表一个决策，每一条路径代表一个决策序列。
  • 问题的状态能够使用一个列表、多维矩阵或树来表示，并且一个状态与其周围的状态存在递推关系。
  • 问题包含最大（小）或最多（少）等最优化描述。

• 求解步骤

  • 描述决策
  • 定义状态
  • 建立DP表
  • 推导状态转移方程
  • 确定边界条件

• 暴力搜索：从上到下，在从下到上

• 记忆化搜搜：从上到下，再从下到上

• 动态规划：直接从下到上来解题

70. 爬楼梯

一维的动态规划问题，分解为子问题，然后从下向上解决

class Solution {public int climbStairs(int n) {if (n <= 2) {return n;}int a = 1;int b = 2;for (int i = 3; i < n; i++) {int tmp = b;b = a + b;a = tmp;}return a + b;}
}

198. 打家劫舍

一维动态规划，特点在于这里的动态转移方程的特点

class Solution {public int rob(int[] nums) {if (nums.length == 1) {return nums[0];}if (nums.length == 2) {return nums[0] > nums[1] ? nums[0] : nums[1];}// 这里动态规划// 描述决策：// 定义状态：dp[i] = max( dp[i-2] + nums[i], nums[i]int a = nums[0];int b = nums[0] > nums[1] ? nums[0] : nums[1];for (int i = 2; i < nums.length; i++) {int tmp = b;b = Math.max(a + nums[i], b);a = tmp;}return b;}
}

第二次编码，看起来写法更加优雅一些，不过其实本质是相同的，而且，上面的解法使用滚动变量的方式，更加节省内存

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

139. 单词拆分

第二次做出来了，这种题的套路都是一个一维的dp数组，这个题的思路是，dp动态记录是否能够被拼接

class Solution {public boolean wordBreak(String s, List<String> wordDict) {boolean[] dp = new boolean[s.length() + 1];Set<String> set = new HashSet<>(wordDict);dp[0] = true;for (int i = 1; i < dp.length; i++) {for (int j = 0; j < i; j++) {if (dp[j] && set.contains(s.substring(j, i))) {dp[i] = true;}}}return dp[s.length()];}
}

322. 零钱兑换

解题思路：
1、维护一个数组，数组大小是amout的大小，然后，遍历每个可能的amount，去和银币比较如果小于银币的大小，那么需要的银币数量就是无穷大
2、如果大于=银币的大小，并且i-coin[j] 里面有值，那么说明可以凑出来
3、那么最小值就重新赋值为memo[i-coin[j] ] + 1

class Solution {public int coinChange(int[] coins, int amount) {// 自底向上的动态规划if(coins.length == 0){return -1;}// memo[n]的值： 表示的凑成总金额为n所需的最少的硬币个数int[] memo = new int[amount+1];memo[0] = 0;for(int i = 1; i <= amount;i++){int min = Integer.MAX_VALUE;for(int j = 0;j < coins.length;j++){if(i - coins[j] >= 0 && memo[i-coins[j]] < min){min = memo[i-coins[j]] + 1;}}// memo[i] = (min == Integer.MAX_VALUE ? Integer.MAX_VALUE : min);memo[i] = min;}return memo[amount] == Integer.MAX_VALUE ? -1 : memo[amount];}
}

300. 最长递增子序列

解题思路：
1、使用动态规划
初始化为值为1的数组
遍历元素
遍历从i=0到j的序列，如果i小于j的值，那么dpi = max(dp[i], dp[j] + 1)

// Dynamic programming.
class Solution {public int lengthOfLIS(int[] nums) {if (nums.length == 0)return 0;int[] dp = new int[nums.length];int res = 0;Arrays.fill(dp, 1);for (int i = 0; i < nums.length; i++) {for (int j = 0; j < i; j++) {if (nums[j] < nums[i])dp[i] = Math.max(dp[i], dp[j] + 1);}res = Math.max(res, dp[i]);}return res;}
}

2、第二个方法，使用动态规划和二分查找的方式
维护一个数组，这个数组是一个子序列
遍历元素，元素二分插入到这个子序列中
替换比他大的第一个元素
最后这个数组的大小就是子序列的大小

在已经构建的递增序列 d[1..len] 中，找到第一个大于等于 nums[i] 的位置，然后用 nums[i] 替换它。

int l = 1, r = len, pos = 0;

变量	含义
l	二分查找的左边界（从 1 开始，因为 d[0] 没用到）
r	二分查找的右边界
pos	记录最后一个满足 d[mid] < nums[i] 的位置，也就是 nums[i] 应该插入的位置的前一个

class Solution {public int lengthOfLIS(int[] nums) {int len = 1, n = nums.length;if (n == 0) {return 0;}int[] d = new int[n + 1];d[len] = nums[0];for (int i = 1; i < n; ++i) {if (nums[i] > d[len]) {d[++len] = nums[i];} else {int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0while (l <= r) {int mid = (l + r) >> 1;if (d[mid] < nums[i]) {pos = mid;l = mid + 1;} else {r = mid - 1;}}d[pos + 1] = nums[i];}}return len;}
}

120. 三角形最小路径和

class Solution {public int minimumTotal(List<List<Integer>> triangle) {int n = triangle.size();int[][] f = new int[n][n];f[0][0] = triangle.get(0).get(0);for (int i = 1; i < n; ++i) {f[i][0] = f[i - 1][0] + triangle.get(i).get(0);for (int j = 1; j < i; ++j) {f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j);}f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i);}int minTotal = f[n - 1][0];for (int i = 1; i < n; ++i) {minTotal = Math.min(minTotal, f[n - 1][i]);}return minTotal;}
}

二刷总结：

你的这段代码是用来求解三角形最小路径和的，但存在多处逻辑错误和边界处理问题，导致计算结果错误。下面逐一分析问题，并给出修正后的代码。

核心问题分析

1. 初始化错误：未累加路径和

matric[i][0] = triangle.get(i).get(0);
matric[i][i-1] = triangle.get(i).get(i-1);

这两行只赋值了当前层的数值，没有累加上层的路径和。例如：

• 第 i 行第 0 列的路径只能来自上一行第 0 列，应该是 matric[i-1][0] + triangle.get(i).get(0)；
• 第 i 行最后一列（索引 i）的路径只能来自上一行最后一列（索引 i-1），但你错误地用了 i-1 作为列索引，且未累加。

2. 循环范围错误：中间列遍历不完整

for (int j = 1; j < i - 1; j++)

这个循环的终止条件 j < i - 1 会导致中间列完全遍历不到（比如 i=2 时，j < 1，循环直接跳过）。正确的中间列范围应该是 1 <= j < i（因为第 i 行有 i+1 个元素，索引 0~i）。

3. 最后一列处理错误

• 第 i 行的最后一列索引是 i（不是 i-1），你漏处理了这一列，且赋值时未累加上层路径和。

4. 结果遍历范围错误

for (int i = 1; i < n; i++)

第 n-1 行的列索引范围是 0~n-1，但你的代码中 matric[i][i-1] 只处理到 n-2 列，最后一列（n-1）未赋值，遍历会读到默认值 0，导致结果错误。

修正后的代码

import java.util.List;class Solution {public int minimumTotal(List<List<Integer>> triangle) {int n = triangle.size();// 二维数组存储到每个位置的最小路径和int[][] dp = new int[n][n];// 初始化顶点dp[0][0] = triangle.get(0).get(0);// 从第二行开始遍历（i从1到n-1）for (int i = 1; i < n; i++) {// 第i行第0列：只能从上一行第0列来dp[i][0] = dp[i-1][0] + triangle.get(i).get(0);// 中间列：j从1到i-1，取上一行j-1和j的最小值 + 当前值for (int j = 1; j < i; j++) {dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + triangle.get(i).get(j);}// 第i行最后一列（索引i）：只能从上一行最后一列（索引i-1）来dp[i][i] = dp[i-1][i-1] + triangle.get(i).get(i);}// 遍历最后一行，找最小值int minSum = dp[n-1][0];for (int j = 1; j < n; j++) {minSum = Math.min(minSum, dp[n-1][j]);}return minSum;}
}

优化（空间复杂度从O(n²)→O(n)）

由于计算第 i 行时只需要第 i-1 行的数据，因此可以用一维数组优化：

import java.util.List;class Solution {public int minimumTotal(List<List<Integer>> triangle) {int n = triangle.size();int[] dp = new int[n];dp[0] = triangle.get(0).get(0);for (int i = 1; i < n; i++) {// 从后往前遍历，避免覆盖未使用的上一行数据dp[i] = dp[i-1] + triangle.get(i).get(i); // 最后一列for (int j = i-1; j > 0; j--) { // 中间列dp[j] = Math.min(dp[j-1], dp[j]) + triangle.get(i).get(j);}dp[0] += triangle.get(i).get(0); // 第一列}int minSum = dp[0];for (int j = 1; j < n; j++) {minSum = Math.min(minSum, dp[j]);}return minSum;}
}

测试用例验证

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]

• 修正前代码结果错误，修正后结果为 11（路径：2→3→5→1），符合预期。

核心逻辑总结：

1. 每个位置的最小路径和 = 上一行相邻位置的最小路径和 + 当前值；
2. 边界列（第一列/最后一列）只有一个来源，中间列有两个来源；
3. 最终结果是最后一行的最小值。

64. 最小路径和

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