动态规划解题思路
1. 状态表示
dp表 里面的值所代表的含义（1.根据题目要求得出 2.经验 + 题目要求 3.分析问题过程中，发现重要子问题）
2. 状态转移方程
dp[i] 等于什么
3. 初始化
保证填表不越界
4. 填表顺序
为了填写该状态的时候，所需的状态已知
5. 返回值
题目要求 + 状态表示
6. 空间优化（平时做题可以不用考虑，面试复习）
一般用到滚动数组（仅仅需要若干状态）
1. 1137. 第 n 个泰波那契数
题目：
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数
n，请返回第 n 个泰波那契数 Tn 的值。
题目链接
1137. 第 N 个泰波那契数 - 力扣（LeetCode）
文字分析
这里还可以进行空间优化：
这里用到 滚动数组，只需要三个数，就可以得到第 i 个数的值，开空间可以节省
代码
class Solution { public:int tribonacci(int n) {int a = 0,b = 1,c = 1;if(n == 0){return 0;}if(n < 3){return 1;}for(int i = 3;i <= n;i++){int d = a + b + c;a = b;b = c;c = d;}return c;} };
2. 08.01 三步问题
题目：
三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
题目链接
11面试题 08.01. 三步问题 - 力扣（LeetCode）
文字分析
注意：
数据过大，储存会有误
在填表的时候，发生加法可以取模
代码
class Solution { public:int waysToStep(int n) {vector<int> s(n + 1);if(n == 1){return 1;} if(n == 2){return 2;} if(n == 3){return 4;}s[0] = 0;s[1] = 1;s[2] = 2;s[3] = 4;for(int i = 4;i <= n;i++){s[i] =( (s[i - 1] + s[i - 2]) % 1000000007 + s[i - 3] )% 1000000007;}return s[n];} };
3. 746 使用最小花费爬楼梯
题目：
给你一个整数数组
cost，其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为
0或下标为1的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
题目链接
746. 使用最小花费爬楼梯 - 力扣（LeetCode）
文字分析
代码
class Solution { public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(n + 1);dp[0] = cost[0];dp[1] = cost[1];for(int i = 2;i < n;i++){dp[i] = min(dp[i - 1] + cost[i],dp[i - 2] + cost[i]);}dp[n] = min(dp[n - 1],dp[n - 2] );return dp[n];} };
