目录

509.斐波那契数

70.爬楼梯 

746.使用最小花费爬楼梯

 总结

---

​​​​​​

用一个数组来存储前两个数的值，然后根据前两个数的值来确定当前的值。

class Solution {
public:
    int fib(int n) {
        if(n<2)  return n;
        vector<int> v;
        v.push_back(0);
        v.push_back(1);
        int num=0,i=2;
        while(v.size()-1<n)
        {
            num=v[v.size()-1]+v[v.size()-2];
            v.push_back(num);
        }
        return v.back();
    }
};

70.爬楼梯

到达当前台阶有多少种方法取决于到达前两个台阶有多少种方法。因为到达当前台阶不是从前一个台阶上来的就是从前前个台阶上来的。

class Solution {
public:
    int climbStairs(int n) {
        if(n<=2)    return n;
        int dp[2]={1,2};
        int ans=0;
        for(int i=3;i<=n;i++)
        {
            ans=dp[0]+dp[1];
            dp[0]=dp[1];
            dp[1]=ans;
        }
        return ans;
    }
};

746.使用最小花费爬楼梯

首先声明一个数组用来存储到达每个台阶所需要的费用，数组的长度应该比cost的长度大1。因为需要爬完整个楼梯，包括最后一个。爬到当前台阶的花费取决于前两个台阶。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        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()];
    }
};

 总结

通过这些简单题来了解动态规划的思想、解题思路、解题步骤。这些题有一个共通的特性，就是如果想要得到当前答案，必须由上面所给出的答案推导而来。

动态规划的步骤：

1. 确定dp数组以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组