动态规划

网上有很多讲动态规划的文章，鱼龙混杂，所以作者在这里就不再多赘述了，推荐一篇觉得写动态规划写的比较好的文章，动态规划理论基础

斐波那契数

斐波那契数

思路

这是一道大家刚刚接触c语言时都写过的题目，相信大家那时基本都是用递归的方法来写的，但递归的复杂度一般都很高，这道题为O(2^N)，显然在算法比赛中这种写法是不适用的。

/* 递归的写法 if(n==0) { return 0; } if(n==1) { return 1; } return fib(n-1)+fib(n-2); */

其实这道题可以用dp来写，因为当前状态dp[i]可以看作是由前两个状态dp[i-1]和dp[i-2]得到的，自然就会想dp的方向想。

//第一步确定dp数组的含义：dp[i] 表示第i个斐波那契数
        int dp[40]={0};
        //第二步确定状态转移方程：dp[i]=dp[i-1]+dp[i-2];
        //第三步：初始化 dp[0]=0,dp[1]=1;
        //第四步：确定遍历顺序,dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
        dp[1]=0,dp[2]=1;
        if(n+1==1)
        {
            return dp[1];
        }
        if(n+1==2)
        {
            return dp[2];
        }
        for(int i=3;i<=n+1;i++)
        {
           dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n+1];

爬楼梯

爬楼梯
其实这道题就是把上面拿到题换了一个表达形式而已。

class Solution {
public:
    int climbStairs(int n) 
    { 
       //第一步：确定dp数组的含义：dp[i]表示爬上第i阶的方法
       vector<int> dp(n+2,0);  //这儿写的时候要注意，不能写成n+1，因为如果n==1的话，那么长度为2，也就只有dp[0],dp[1]这两个元素了，会造成空指针的访问问题
       //第二步：确定状态转移方程，dp[i]=dp[i-1]+dp[i-2],因为到达第i层，只有从第i-1或者i-2 
       //层才能到达
       //第三步：初始化：dp[1]=1,dp[2]=2
       //第四步：确定遍历顺序，很显然，我们要从前面的状态推导到后面的状态，因此要顺序遍历
       dp[1]=1,dp[2]=2;
       if(n==1) return 1;
       if(n==2) return 2;
       for(int i=3;i<=n;i++)
       {
           dp[i]=dp[i-1]+dp[i-2];
       }       
       return dp[n];
    }
};

使用最小花费爬楼梯

使用最小花费爬楼梯

这一题和前面两个依然很类似，只不过中间掺杂了一个费用这个量。
注意：这道题虽然简单，但是在理解题意时一定要注意，理解dp数组时一定要深刻，结合题目做到合理的理解。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        //第一步：确定dp数组的含义：dp[i]表示爬到第i个台阶的最低花费,并且你可以选择从第i层往上爬了
        //也就是说你花费了cost[i]。
        int size=cost.size(); //下标为size的地方是楼顶
        vector<int> dp(size,0);
        //第二步：初始化：dp[1]=cost[0],dp[2]=min(cost[0],cost[1]); （这是一开始错误的理解方式）
        //第三步：确定状态转移方程：dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); （这是一开始错误的理解方式）
        //第四步：确定遍历顺序：因为状态转移方程是从前一个状态推导后面一个状态，所以是顺序遍历
        //dp[1]=cost[0],dp[2]=min(cost[0],cost[1]); //注意题目中说的那句话，你可以从第0层或第1层
                                                  // 开始爬楼梯，也就是说你的起点可以由两种不同的
                                                  //选择方式，正好对应了dp状态转移方程需要的两个
                                                  //初始化，再结合dp数组的定义，因此
                                                  //dp[0]=cost[0],dp[1]=cost[1];
        dp[0]=cost[0],dp[1]=cost[1];
        for(int i=2;i<size;i++)
        {
            //dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);对dp数组理解的不够深刻
            dp[i]=min(dp[i-1],dp[i-2])+cost[i];
        }
        return min(dp[size-1],dp[size-2]);  //从我们dp数组的定义看，到第i层时，需要把自己这一层往上爬的费用也付了，因此只要比较最后一层和最后两层的最小值即可，因为根据我们dp数组的定义可以得到。
    }
};