动态规划解决泰波那契数列，爬楼梯最小花费问题

做题之前���们需要先搞清楚解决动态规划的几个步骤

1 状态表示，准备一个dp表

2 状态转移方程 

3 初始化

4 填表

5 返回值

步骤1 状态表示，准备dp表

dp[0]

dp[1]

dp[2]

dp[3]

dp[4] = dp[0]+dp[1]+dp[3]

步骤2 状态转移方程表示

dp[i] = dp[i-1]+dp[i-2]+dp[i-3]

步骤3 4 5 都是对代码的细节处理，代码如下

#define _CRT_SECURE_NO_WARNINGS 1#include#includeint ret(int n){    int dp[38] = { 0 };    int i = 0;    if (n == 0)        return 0;    if (n == 1 || n == 2)        return 1;    dp[0] = 0, dp[1] = dp[2] = 1;    for (i = 3; i      
 
   
根据上面两个图所示，我们可以得到到楼顶的最小花费
  
dp[i] = min(dp[i-1]+cost[i-1] ,dp[i-2]+cost[i-2])
   
class Solution {public:    int minCostClimbingStairs(vector& cost) {           int n = cost.size();    vector dp(n+1);    for(int i = 2;i