从本篇开始总结的是动态规划的一些内容，动态规划是算法中非常重要的一个版块，因此也是学习算法中的一个重点，在学习动态规划前应当要把动态规划的基础知识学习一下
算法原理
动态规划既然是一个新的算法，这个名字也是新名字，那么就要首先明确这个算法的名字代表什么含义
动态规划是什么？
动态规划其实就是dp表中的值所表示的含义
那什么又是dp表？
dp表是解决这类问题中必须要使用的一个内容，通常是借助vector来表示
dp表怎么写出来？
一般来说题目要求中会有一些提示，同时在分析问题的过程中，如果遇到了分析的过程中有重复的子问题，也可以借助这个逻辑写出一个状态转移方程，利用这个状态转移方程就可以填写到dp表中
状态转移方程
状态转移方程就是在动态规划中根据一部分提示找到dp表的填入方法，再根据这个方法就可以借助dp表解决问题，因此状态转移方程是解决问题的关键
题目解析
首先用一个比较简单的题目来上手动态规划
第n个泰波那契数列
对于这个题来说，可以用上面的动态规划的方法来处理：
首先创建一个dp表，再从题目中找到状态转移方程，再利用状态转移方程写入dp表，再利用dp表求出要找的数据
class Solution { public: int tribonacci(int n) { // 处理边界 if(n==0) { return 0; } if(n==1 || n==2) { return 1; } // 创建dp表 vector<int> dp(n+1); // 初始化dp表 dp[0]=0; dp[1]=1; dp[2]=1; //填入dp表 for(int i=3;i<=n;i++) { dp[i]=dp[i-1]+dp[i-2]+dp[i-3]; } // 返回值 return dp[n]; } };
三步问题
分析问题：
假设现在有1个台阶，那么小孩跳到这个台阶的方法有1种，直接从地面走到第一个台阶上
假设现在有2个台阶，那么小孩跳到这个台阶的方法有2种，第一种从地面直接走到第二个台阶上，第二种是小孩从地面走到第一个台阶，再从第一个台阶走到第二个台阶上
假设现在有3个台阶，那么小孩跳到这个台阶的方法有4种，第一种直接跳到第三个台阶上，第二种先跳到第一个台阶，再从第一个台阶向第三个台阶跳，而从第一个台阶向第三个台阶跳又有两种，参考有2个台阶的方案，那么总共第二种方法有2种，第三种小孩跳到第二个台阶，再从第二个台阶跳到第三个台阶，因此总共有四种方法
假设现在有4个台阶，那么小孩跳到第四个台阶的方法总共有7种，先让小孩走到第一个台阶，再从第一个台阶走到第四个台阶即可，而小孩走到第一个台阶的方法有1种；也可以先让小孩走到第二个台阶，再从第二个台阶走到第四个台阶，而小孩走到第二个台阶的方法有2种；先让小孩走到第三个台阶，再从第三个台阶直接到第四个台阶，而直接让小孩走到第四个台阶的方法有4种，因此上面的这些总计是7种
假设现在有5个台阶，那么小孩跳到第五个台阶的方法有13种，先让小孩跳到第二个台阶，再从第二个台阶直接到第五个台阶…
因此规律就找到了，其实就是一个斐波那契数列的变形问题，利用上面的例题的思路就可以解决这个问题
class Solution { public: int waysToStep(int n) { vector<long long> dp(n+4); dp[0]=0; dp[1]=1; dp[2]=2; dp[3]=4; for(int i=4;i<=n;i++) { dp[i]=dp[i-1]+dp[i-2]+dp[i-3]; dp[i] %= 1000000007; } return dp[n]; } };
使用最小花费爬楼梯
此题也是动态规划中的一个典型题，这里从两个角度来看这道题
从最开始的介绍中可以知道，对于动态规划的问题来说，关键是dp[i]的意义和状态转移方程，在解决问题的过程中要优先对这两个部分进行思考和解决，那么两个不同的dp[i]的角度来看这个题
首先从第一个角度来看：
如果这里的dp[i]表示的是，上到第i个台阶需要花费多少钱：
那么可以这样思考问题，要知道上到第i个台阶需要多少钱，就必然要知道上到第i-1个台阶要花多少钱，再用这个钱加上上第i-1个台阶要花多少钱，由于一次可以上两个台阶，因此也要知道上到第i-2个台阶需要多少钱和上这个台阶需要多少钱，再比较一下从第i-1个台阶上划算还是从第i-2个台阶上划算，比较后就可以得到dp[i]的值，因此状态转移方程就很容易得到了
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
此时注意一下边界初始化问题：在第0和第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[i]对应的意义还有其他，这里还可以理解为从第i个位置上到最顶上需要的花费，因此这里也可以借助这个意义来解决
那如果要求从第i个台阶上到顶端要花多少钱，需要知道从第i个台阶一次上一个台阶还是一次上两个台阶比较划算，因此这里又需要知道i+1和i+2的值，根据这两个的值决定一次上一个台阶还是上两个台阶，因此状态转移方程也可以得出来了：
dp[i]=min(dp[i+1]+cost[i],dp[i+2]+cost[i]);
那么代码的实现也可以得出：
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]); } };
