SYSTEM
今日动态规划刷题笔记(5道高频简单/中等,无Hard)
src/content/notes/algorithm/动态规划.md 今日动态规划刷题笔记(5道高频简单/中等,无Hard)
覆盖题目:LC70爬楼梯、LC121买卖股票最佳时机、LC53最大子数组和、LC198打家劫舍、LC322零钱兑换 分类:一维线性DP、Kadane子数组DP、完全背包DP
一、LC70 爬楼梯|基础一维DP
题意
一次爬1或2阶,求爬到第n阶的总方法数。
核心思路
- 状态定义:
dp[i]= 爬到第i阶楼梯的总方案数 - 转移逻辑:到i阶只能从i-1(爬1步)、i-2(爬2步)过来 $$dp[i] = dp[i-1] + dp[i-2]$$
- 初始化边界:
- dp[0] = 1(0阶原地不动,1种方案)
- dp[1] = 1(1阶只有1种)
- 遍历: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;
}
}
代码细节
- 边界判断n=1、n=2直接返回,避免循环;
- 滚动变量a、b替代dp数组,节省O(n)空间;
- 递推无取min/max,纯累加计数。
题型规律
计数类一维DP:当前结果仅依赖前两项,滚动双变量压缩空间。
二、LC121 买卖股票的最佳时机|最值型一次遍历DP
题意
只能一次买入、之后一天卖出,求最大利润;无盈利返回0。
核心思路
- 状态拆分(等价DP思想):
- minPrice:dp[i-1],前i天历史最低买入价
- maxProfit:全局最优,前i天最大利润
- 转移逻辑:
- 当天价格比历史最低价低 → 更新最低价
- 否则计算当天卖出利润,更新全局最大利润
- 初始化: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;
}
}
代码细节
Integer.MAX_VALUE初始化最小值,是找最小变量固定套路;- 利润只取更大值,初始0天然兼容全下跌数组;
- 无需dp数组,单趟遍历O(n)、O(1)空间。
题型规律
单状态最值DP:只维护历史最优值,不需要保存全部dp数组,一次遍历完成。
三、LC53 最大子数组和|Kadane一维DP
题意
找连续子数组,返回元素和最大值,子数组至少1个元素。
核心思路
- 状态定义:
- sum = dp[i]:以当前i结尾的最大连续子数组和
- maxSum:全局最大子数组和
- 转移方程: $$dp[i] = Math.max(nums[i], dp[i-1] + nums[i])$$ 两种选择:新开子数组 / 接上前面的子数组
- 每次计算完dp[i],更新全局最大值maxSum
- 初始化: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;
}
}
代码细节
- 仅保留前一项dp[i-1],单变量滚动,空间O(1);
- 不能初始maxSum=0,数组全负数时会返回0错误;
- 转移核心是
Math.max(当前元素, 前序和+当前元素)。
题型规律
连续子数组最值DP:dp[i]定义为「以i结尾」,仅依赖前一个状态,单变量压缩。
四、LC198 打家劫舍|相邻约束一维DP
题意
不能偷相邻房屋,求能偷到的最大金额。
核心思路
- 状态定义:dp[i] = 前i间房屋最大金额
- 转移方程: $$dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])$$ 两种选择:不偷当前(继承dp[i-1]) / 偷当前(dp[i-2]+当前金额)
- 初始化:
- dp[0] = nums[0]
- dp[1] = Math.max(nums[0], nums[1])
- 空间优化: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;
}
}
代码细节
- 需要两个滚动变量,因为转移依赖i-1、i-2两个前置状态;
- 边界单独判断空数组、单元素数组;
- 每次循环完成滚动赋值:旧prev1给prev2,新curr给prev1。
题型规律
相邻约束最值DP:当前状态依赖前两项,双变量滚动压缩空间。
五、LC322 零钱兑换|完全背包DP
题意
硬币无限供应,凑amount总金额,求最少硬币数;无法凑成返回-1。
核心思路
- 状态定义:
dp[i]= 凑金额i需要的最少硬币数量 - 初始化:
- dp[0] = 0,凑0元需要0枚硬币;
- 其余dp[i] = amount+1(无穷大标记,代表暂时不可达)
- 转移方程(完全背包,硬币可重复选): $$dp[i] = Math.min(dp[i], dp[i - coin] + 1)$$
- 结果判定: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];
}
}
代码细节
- 初始化极大值
amount+1,区分合法/不合法金额; - 两层循环:外层遍历金额、内层遍历硬币(完全背包正序遍历);
dp[i-coin]+1:取一枚当前硬币,硬币数量+1;- 最后必须判断是否超出上限,否则会返回错误大数。
题型规律
背包类DP:dp数组容量为目标值;完全背包正序遍历容量,01背包倒序遍历容量;求最少/最多数量用min/max转移。
通用DP解题固定四步模板(所有题通用)
- 定义dp含义
- 线性一维:dp[i]代表前i个元素 / 以i结尾的最优解
- 背包:dp[i]代表凑出i容量/金额的最优解
- 推导状态转移方程
- 计数类:
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)(零钱兑换)
- 计数类:
- 初始化边界
- 0值基准:dp[0]=0(爬楼梯、零钱兑换)
- 极值初始化:找min用MAX_VALUE,找max用MIN_VALUE;不可达状态设超大数
- 单元素、空数组单独判边界
- 遍历顺序 + 空间优化
- 仅依赖前1项:单变量滚动(53、121)
- 依赖前2项:双变量滚动(70、198)
- 背包问题:必须保留dp数组,无法压缩一维变量
- 输出结果
- 线性题: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),不可压缩到常数 |
高频踩坑汇总
- 最值初始化错误:求最大值不能初始0(全负数数组翻车,如LC53);
- 数组越界:dp数组长度必须是
n+1(背包、爬楼梯); - 滚动变量更新顺序错误:必须先算curr,再平移prev2、prev1;
- 背包未判断合法值:直接返回dp[amount]会输出极大数,需要兜底返回-1;
- 边界遗漏:空数组、长度为1的输入,不加判断会数组越界。