动态规划（斐波那契数列模型）
1. 第 N 个泰波那契数
- 状态表示
dp[i]所表示的含义，那么这个状态表示怎么来的那？
题目要求、经验根据题目要求、分析问题的过程中发现重复子问题
- 状态转移方程
- dp[i]等于什么。根据这题的题目我们发现
d[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] - 初始化
保证填表的时候不越界 - 填表顺序
为了填写当前的状态，所需的状态已经完成了 - 返回值
这个题目的返回值当然就是dp[n]了 - AC代码：
class Solution { public: int tribonacci(int n) { if (n == 0 || n == 1) return n; vector<int> dp(n + 1); dp[0] = 0, dp[1] = 1, dp[2] = 1; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; } return dp[n]; } };
优化之后：
AC代码：
class Solution { public: int tribonacci(int n) { if (n == 0) return 0; if (n == 1 || n == 2) return 1; int a = 0, b = 1, c = 1, d = 0; for (int i = 3; i <= n; i++) { d = a + b + c; a = b; b = c; c = d; } return d; } };
2. 三步问题
- 状态表示
dp[i]表示：到达i位置时，一共有多少中走法 - 状态转移方程
- 初始化
- 填表
- 返回值
AC代码：
class Solution { const int mod = 1e9 + 7; public: int waysToStep(int n) { if (n == 1) return 1; if (n == 2) return 2; if (n == 3) return 4; vector<int> dp(n + 1); dp[1] = 1, dp[2] = 2, dp[3] = 4; for (int i = 4; i <= n; i++) { dp[i] = ((dp[i - 1] + dp[i - 2]) % mod + dp[i - 3]) % mod; } return dp[n]; } };
这个题目三个值都加起来，再取模是不行的。这里我们没计算一次加法（乘法）都要进行一次取模运算
3. 使用最小花费爬楼梯
解法一
- 状态表示
dp[i]表示到达i位置的最小花费 - 状态转移方程
- 初始化
- 填表顺序
- 返回值
AC代码：
class Solution { public: int minCostClimbingStairs(vector<int>& cost) { int len = cost.size(); vector<int> dp(len + 1); for (int i = 2; i <= len; i++) { dp[i] = min((dp[i - 1] + cost[i - 1]), (dp[i - 2] + cost[i - 2])); } return dp[len]; } };
解法二
- 状态表示
dp[i]从i位置出发，到达楼顶所需的最小花费 - 状态转移方程
- 初始化
dp[n - 1] = cost[n - 1], dp[n - 2] = cont[n - 2] - 填表
从左往右
- 返回值
min(dp[0], dp[1])
AC代码：
class Solution { public: int minCostClimbingStairs(vector<int>& cost) { int n = cost.size(); vector<int> dp(n); dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2]; for (int i = n - 3; i >= 0; i--) { dp[i] = min((dp[i + 1] + cost[i]), (dp[i + 2] + cost[i])); } return min(dp[0], dp[1]); } };
4. 解码方法
- 状态表示
以i位置为结尾，有多少种解码方法 - 状态转移方程
- 初始化
dp[0] = 1 或者0dp[1]也有三种情况 0 、1 、2
- 填表
- 返回值
AC代码：
class Solution { public: int numDecodings(string s) { int n = s.size(); vector<int> dp(n + 1); if (s[0] == '0') dp[0] = 0; else dp[0] = 1; if (n == 1) return dp[0]; if (s[1] >= '1' && s[1] <= '9') dp[1] += dp[0]; int t = (s[0] - '0') * 10 + s[1] - '0'; if (t >= 10 && t <= 26) dp[1] += 1; for (int i = 2; i < n; i++) { if (s[i] >= '1' && s[i] <= '9') dp[i] += dp[i - 1]; int t = (s[i - 1] - '0') * 10 + s[i] - '0'; if (t >= 10 && t <= 26) dp[i] += dp[i - 2]; } return dp[n - 1]; } };
还可以使用辅助节点的方式来处理这个题目的边界问题：
需要注意的是：
- 辅助节点里面的值要保证后续填表是正确的
- 下标的映射关系
