← 返回学习路线

SYSTEM

今日动态规划刷题笔记(5道高频简单/中等,无Hard)

LeetCode题解
src/content/notes/algorithm/动态规划.md

今日动态规划刷题笔记(5道高频简单/中等,无Hard)

覆盖题目:LC70爬楼梯、LC121买卖股票最佳时机、LC53最大子数组和、LC198打家劫舍、LC322零钱兑换 分类:一维线性DP、Kadane子数组DP、完全背包DP

一、LC70 爬楼梯|基础一维DP

题意

一次爬1或2阶,求爬到第n阶的总方法数。

核心思路

  1. 状态定义:dp[i] = 爬到第i阶楼梯的总方案数
  2. 转移逻辑:到i阶只能从i-1(爬1步)、i-2(爬2步)过来 $$dp[i] = dp[i-1] + dp[i-2]$$
  3. 初始化边界:
    • dp[0] = 1(0阶原地不动,1种方案)
    • dp[1] = 1(1阶只有1种)
  4. 遍历:i从2到n;空间可优化为O(1)双变量滚动

完整代码(空间优化版,面试推荐)

class Solution {
    public int climbStairs(int n) {
        if(n <= 2) return n;
        int a = 1; // dp[i-2]
        int b = 2; // dp[i-1]
        int res = 0;
        for(int i = 3; i <= n; i++){
            res = a + b;
            a = b;
            b = res;
        }
        return b;
    }
}

代码细节

  1. 边界判断n=1、n=2直接返回,避免循环;
  2. 滚动变量a、b替代dp数组,节省O(n)空间;
  3. 递推无取min/max,纯累加计数。

题型规律

计数类一维DP:当前结果仅依赖前两项,滚动双变量压缩空间。


二、LC121 买卖股票的最佳时机|最值型一次遍历DP

题意

只能一次买入、之后一天卖出,求最大利润;无盈利返回0。

核心思路

  1. 状态拆分(等价DP思想):
    • minPrice:dp[i-1],前i天历史最低买入价
    • maxProfit:全局最优,前i天最大利润
  2. 转移逻辑:
    • 当天价格比历史最低价低 → 更新最低价
    • 否则计算当天卖出利润,更新全局最大利润
  3. 初始化:minPrice = Integer.MAX_VALUE(极大值保证首日赋值),maxProfit=0(亏损返回0)

完整代码

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for(int p : prices){
            if(p < minPrice){
                minPrice = p;
            }else{
                maxProfit = Math.max(maxProfit, p - minPrice);
            }
        }
        return maxProfit;
    }
}

代码细节

  1. Integer.MAX_VALUE 初始化最小值,是找最小变量固定套路;
  2. 利润只取更大值,初始0天然兼容全下跌数组;
  3. 无需dp数组,单趟遍历O(n)、O(1)空间。

题型规律

单状态最值DP:只维护历史最优值,不需要保存全部dp数组,一次遍历完成。


三、LC53 最大子数组和|Kadane一维DP

题意

找连续子数组,返回元素和最大值,子数组至少1个元素。

核心思路

  1. 状态定义:
    • sum = dp[i]:以当前i结尾的最大连续子数组和
    • maxSum:全局最大子数组和
  2. 转移方程: $$dp[i] = Math.max(nums[i], dp[i-1] + nums[i])$$ 两种选择:新开子数组 / 接上前面的子数组
  3. 每次计算完dp[i],更新全局最大值maxSum
  4. 初始化:sum、maxSum都等于nums[0],兼容全负数数组

完整代码

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = nums[0];
        int maxSum = nums[0];
        for(int i = 1; i < nums.length; i++){
            sum = Math.max(nums[i], sum + nums[i]);
            maxSum = Math.max(maxSum, sum);
        }
        return maxSum;
    }
}

代码细节

  1. 仅保留前一项dp[i-1],单变量滚动,空间O(1);
  2. 不能初始maxSum=0,数组全负数时会返回0错误;
  3. 转移核心是Math.max(当前元素, 前序和+当前元素)。

题型规律

连续子数组最值DP:dp[i]定义为「以i结尾」,仅依赖前一个状态,单变量压缩。


四、LC198 打家劫舍|相邻约束一维DP

题意

不能偷相邻房屋,求能偷到的最大金额。

核心思路

  1. 状态定义:dp[i] = 前i间房屋最大金额
  2. 转移方程: $$dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])$$ 两种选择:不偷当前(继承dp[i-1]) / 偷当前(dp[i-2]+当前金额)
  3. 初始化:
    • dp[0] = nums[0]
    • dp[1] = Math.max(nums[0], nums[1])
  4. 空间优化:prev2=dp[i-2],prev1=dp[i-1],滚动更新

空间优化代码(推荐)

class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        int prev2 = nums[0];
        int prev1 = Math.max(nums[0], nums[1]);
        for(int i = 2; i < nums.length; i++){
            int curr = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}

代码细节

  1. 需要两个滚动变量,因为转移依赖i-1、i-2两个前置状态;
  2. 边界单独判断空数组、单元素数组;
  3. 每次循环完成滚动赋值:旧prev1给prev2,新curr给prev1。

题型规律

相邻约束最值DP:当前状态依赖前两项,双变量滚动压缩空间。


五、LC322 零钱兑换|完全背包DP

题意

硬币无限供应,凑amount总金额,求最少硬币数;无法凑成返回-1。

核心思路

  1. 状态定义:dp[i] = 凑金额i需要的最少硬币数量
  2. 初始化:
    • dp[0] = 0,凑0元需要0枚硬币;
    • 其余dp[i] = amount+1(无穷大标记,代表暂时不可达)
  3. 转移方程(完全背包,硬币可重复选): $$dp[i] = Math.min(dp[i], dp[i - coin] + 1)$$
  4. 结果判定:dp[amount] > amount 说明无法凑出,返回-1

完整代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        int initMax = amount + 1;
        for(int i = 1; i <= amount; i++){
            dp[i] = initMax;
        }
        dp[0] = 0;
        for(int i = 1; i <= amount; i++){
            for(int coin : coins){
                if(coin <= i){
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > initMax ? -1 : dp[amount];
    }
}

代码细节

  1. 初始化极大值amount+1,区分合法/不合法金额;
  2. 两层循环:外层遍历金额、内层遍历硬币(完全背包正序遍历);
  3. dp[i-coin]+1:取一枚当前硬币,硬币数量+1;
  4. 最后必须判断是否超出上限,否则会返回错误大数。

题型规律

背包类DP:dp数组容量为目标值;完全背包正序遍历容量,01背包倒序遍历容量;求最少/最多数量用min/max转移。


通用DP解题固定四步模板(所有题通用)

  1. 定义dp含义
    • 线性一维:dp[i]代表前i个元素 / 以i结尾的最优解
    • 背包:dp[i]代表凑出i容量/金额的最优解
  2. 推导状态转移方程
    • 计数类:dp[i] = dp[i-1] + dp[i-2](爬楼梯)
    • 最值二选一:dp[i] = max(dp[i-1], dp[i-2]+val)(打家劫舍)
    • 子数组两种选择:dp[i] = max(nums[i], dp[i-1]+nums[i])(最大子数组)
    • 背包取最小:dp[i] = min(dp[i], dp[i-coin]+1)(零钱兑换)
  3. 初始化边界
    • 0值基准:dp[0]=0(爬楼梯、零钱兑换)
    • 极值初始化:找min用MAX_VALUE,找max用MIN_VALUE;不可达状态设超大数
    • 单元素、空数组单独判边界
  4. 遍历顺序 + 空间优化
    • 仅依赖前1项:单变量滚动(53、121)
    • 依赖前2项:双变量滚动(70、198)
    • 背包问题:必须保留dp数组,无法压缩一维变量
  5. 输出结果
    • 线性题:dp[n-1] / 滚动后的最后变量
    • 背包题:dp[target],并判断是否合法

五类DP核心区分速记

题目 DP类型 依赖前置 空间优化方案
LC70 爬楼梯 一维计数DP i-1、i-2 双变量滚动O(1)
LC121 股票 单状态最值DP i-1历史最优 两个变量O(1)
LC53 最大子数组 Kadane子数组DP i-1 单变量滚动O(1)
LC198 打家劫舍 相邻约束最值DP i-1、i-2 双变量滚动O(1)
LC322 零钱兑换 完全背包DP 0~i-coin 一维数组O(amount),不可压缩到常数

高频踩坑汇总

  1. 最值初始化错误:求最大值不能初始0(全负数数组翻车,如LC53);
  2. 数组越界:dp数组长度必须是n+1(背包、爬楼梯);
  3. 滚动变量更新顺序错误:必须先算curr,再平移prev2、prev1;
  4. 背包未判断合法值:直接返回dp[amount]会输出极大数,需要兜底返回-1;
  5. 边界遗漏:空数组、长度为1的输入,不加判断会数组越界。