解题思想
什么是动态规划？
动态规划的核心思想：每一个状态都是由上一个状态推导出来的，即dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。
作为对比，贪心没有状态推导，而是局部直接选最优，例如每次拿物品都选一个最大的，和上一个状态没有关系。
题目体系
- 基础动态规划：斐波那契数列、爬楼梯
- 背包问题
- 01背包：分割等和子序列
- 完全背包：
- 打家劫舍：打家劫舍 I-II-III
- 股票问题：买卖股票最佳时机 I-II-III-IV
- 子序列问题
- 非连续子序列：最长公共子序列
- 连续子序列：最长重复子数组、最大子序和
- 编辑距离：判断子序列、编辑距离
- 回文串：回文子串、最长回文子序列
动规解题步骤
对于任意一道动态规划题目，都应遵循如下五部解决：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
509. 斐波那契数
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
思路
按照动规解题步骤：
- dp数组及其下标含义：数
n的斐波那契数值为F(n) - 递推公式：题中已给出
dp[i] = dp[i-1] + dp[i-2] - 数组初始化：题中已给出
dp[0]=0; dp[1]=1; - 遍历顺序：根据公式，状态
i依赖于状态i-1和i-2，因此从小到大遍历 - 举例推导：手算即可得[0,10]的斐波那契数列为 “0 1 1 2 3 5 8 13 21 34 55”
代码实现
不难想到完整计算出到目标数n的斐波那契数列，随后直接输出即可
时间复杂度：$O(n)$，空间复杂度：$O(n)$
class Solution {
public:
int fib(int n) {
if(n<=1) return n;
vector<int> dp(n+1); //容器长度为n+1
dp[0] = 0;
dp[1] = 1;
for(int i=2; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};
但实际上，计算目标数k的斐波那契值，只需要保存k-1和k-2即可
时间复杂度：$O(n)$，空间复杂度：$O(1)$
class Solution {
public:
int fib(int n) {
if(n<=1) return n;
int dp[2]; // 数组大小为2
dp[0] = 0;
dp[1] = 1;
for(int i=2; i<=n; i++){
int sum = dp[0]+dp[1];
dp[0] = dp[1];
dp[1] = sum;
}
return dp[1];
}
};
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
规定1 <= n <= 45
示例 ：
输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
思路
按照动规解题步骤：
- dp数组及其下标含义：
n阶台阶的爬法共有dp[n]种 - 递推公式：对于
n阶最终只有两种情况，已爬到n-1阶，再爬一阶；已爬到n-2阶，再爬两阶。因此本阶爬法是下两阶爬法之和dp[n] = dp[n-1] + dp[n-2] - 数组初始化：已知
n>=1，定义dp[1]=1; dp[2]=2; - 遍历顺序：上台阶的遍历顺序一定是从前向后遍历的
- 举例推导：手写出一个5阶台阶的推导结果串为“1, 2, 3, 5, 8”
问题：
- 对于第n阶的爬法F(n)，最终只有两种情况，已爬到n-1阶，再爬一阶；已爬到n-2阶，再爬两阶，那么能否F(n)=F(n-1)+F(n-2)？问题在于
F(n-1) & F(n-2)有没有重复项。
伪命题，最终结果都不一样，过程怎么可能存在完全一样 而且就算前面爬的都一样，最后一步也必定是一个不同的 1 或 2： [1,1,1] + 2 vs. [1,1,1,1] + 1
代码实现
class Solution {
public:
int climbStairs(int n) {
vector<int> dp(n+2); // 为避免dp[2]出现空指针，也可以直接对初始值 return n 处理
dp[1]=1;
dp[2]=2;
for(int i=3; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};
与斐波那契数列问题本质相同，因此也可以做出空间优化
class Solution {
public:
int climbStairs(int n) {
if (n <= 1) return n; // 针对n=1打的补丁
int dp[3];
dp[1]=1;
dp[2]=2;
for(int i=3; i<=n; i++){
int sum = dp[1]+dp[2];
dp[1] = dp[2];
dp[2] = sum;
}
return dp[2];
}
};
746. 使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。 - 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。
思路
按照动规解题步骤：
- dp数组及其下标含义：到达
i阶的最小花费为dp[i] - 递推公式：可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。
- dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。
- dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。
- 因此最小花费为：
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
- 数组初始化：初始楼梯任选即
dp[0]=0; dp[1]=0; - 遍历顺序：爬楼梯的遍历顺序一定是从前向后遍历的
- 举例推导：
代码实现
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(cost.size()+1);
dp[0]=0;
dp[1]=0;
for(int i=2; i<=cost.size(); i++){
dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
}
return dp[cost.size()];
}
};
后记
动态规划的核心在于递推公式的设计，它是循环体的主要部分；
此外，数组初始化决定了循环前dp数组的初值和长度、dp数组及其下标含义+遍历顺序共同决定了循环条件的设计。
