代码随想录算法训练营第二十八天| 509. 斐波那契数 , 70. 爬楼梯 , 746. 使用最小花费爬楼梯

今天是动态规划学习的第一天，首先学习了动态规划做题的五个步骤，然后接触了一些动态规划的题目。

理论基础

动态规划指的是，每一个状态都是由前面的状态推导求解的。动态规划的题目我们一般分为下面的五个步骤：

1.确定dp数组中元素的含义是什么

2.确实递推公式

3.确定dp数组如何进行初始化

4.确定递推的顺序

5.举例推导一下dp数组，验证是否可行

509. 斐波那契数

题目链接：509. 斐波那契数 - 力扣（LeetCode）

我们用我们的五个步骤来做这个题。对于dp数组的元素含义，dp[i]表示第i个斐波那契数的数值；递推公式题目已经给出了，dp[i]=dp[i-1]+dp[i-2];初始化只需要dp[0]=0,dp[1]=1,递推顺序是从小到大。上述信息确定之后这个题目也就做出来了，具体代码实现如下：
 

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

70. 爬楼梯

题目链接：70. 爬楼梯 - 力扣（LeetCode）

对于dp[i]的含义，我们定义为爬到i阶有多少种方法；由于爬楼梯只能爬1步或2步，所以dp[i]=dp[i-1]+dp[i-2];对于初始化，我们将dp[0]=0,dp[1]=1,dp[2]=2;递推顺序依然是从小到大进行递推。用3验证一下是满足要求的。具体代码实现如下：
 

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

 746. 使用最小花费爬楼梯

题目链接：746. 使用最小花费爬楼梯 - 力扣（LeetCode）

这个题目的意思是cost数组对应的是上台阶的花费，花费cost[i]后可以选择走一步或两步台阶。可以从0出发或1出发。求解到达顶部的最少花费。

首先我们用dp[i]表示到达i所需要的最低花费；对于递推公式，我们可以选择从i-2跳上来或i-1跳上来，选择的应该是花费较少的那种方法，所以dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);初始化我们选择dp[0]=0,dp[1]=0;递推顺序依旧是从小到大递推；使用题目给的示例进行验证是没有问题的。具体代码实现如下：
 

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int dp[cost.size()+10];
        dp[0]={0};
        dp[1]={0};
        for(int i=2;i<=cost.size();i++)
        {
            dp[i]=min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]);
        }
        return dp[cost.size()];
    }
};