动态规划刷题总结
动态规划算法描述
动态规划（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 设为 0
while (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），符合预期。
核心逻辑总结：
- 每个位置的最小路径和 = 上一行相邻位置的最小路径和 + 当前值；
- 边界列（第一列/最后一列）只有一个来源，中间列有两个来源；
- 最终结果是最后一行的最小值。
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];
}
}
浙公网安备 33010602011771号