day32|leetcode 509.斐波那契数，70.爬楼梯，746.使用最小花费爬楼梯

动态规划

动态规划理论基础：

题目分类：

• 背包问题

• 打家劫舍

• 股票问题

• 子序列问题

关键：

• dp数组以及下标的含义

• 递归公式

• dp数组如何初始化

• 遍历顺序

如果无法通过就打印dp数组看看问题出在哪里

1.斐波那契数组

经典动态规划入门题:

动态规划五部曲：

1. 确定dp[i]的含义：第i个斐波那契数

2. 递推公式：dp[i]=dp[i-1]+dp[i-2]

3. dp数组如何初始化：dp[0]=0,dp[1]=1

4. 遍历顺序：从前往后

5. 打印dp数组

class Solution {
public:
    int fib(int n) {
      if(n<2)return n;
      vector<int>dp(n+1);
      //初始化
      dp[0]=0;
      dp[1]=1;
​
      for(int i=2;i<=n;i++)
      {
        dp[i]=dp[i-1]+dp[i-2];
      }
    return dp[n];
    }
};

2.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

分析：

爬到第1阶：有1种方法

爬到第2阶：有2种方法

爬到第3阶：有3种方法（1 1 1，1 2，2 1）

爬到第四阶：有5种方法（1111，22，121，112，211）

使用动态规划：

1. dp[i]含义：爬到第i阶有dp[i]种方法

2. 递推公式：dp[i]=dp[i-1]+dp[i-2]

3. dp数组如何初始化：dp[1]=1,dp[2]=2

4. 遍历顺序：从1到n

5. 打印dp

class Solution {
public:
    int climbStairs(int n) {
       if(n<3)return n;
       vector<int>dp(n+1);
       //初始化
       dp[1]=1;
       dp[2]=2;
       for(int i=3;i<=n;i++)
       {
         dp[i]=dp[i-1]+dp[i-2];
       }
    return dp[n];
    }
};

3.使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

动态规划：

1. dp[i]含义：到达第i阶最小花费为多少

2. 递推公式：dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]),因为可以选择一次爬一阶还是两阶

3. 初始化：由题你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。意思是：dp[0]=0,dp[1]=0,从0或者1开始并不需花费，只有向上爬才要花费

4. 遍历顺序：从前往后遍历

5. 打印dp数组

注意：cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。

输入：cost = [10,15,20]
         下标：0  1  2
最终爬到的是第三阶dp[3]
所以for循环中i<=cost.size();取等，才能通过i++，达到终点3

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        if(cost.size()<=1)return 0;//1阶，不用爬
        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()];
    }
};

ps:开启新篇章！动态规划！