Day38 | 509. 斐波那契数, 70. 爬楼梯, 746. 使用最小花费爬楼梯

理论基础

重点在于方法论的使用上面：

1、确定dp数组（dp table）以及下标的含义

2、确定递推公式

3、dp数组如何初始化

4、确定遍历顺序

5、举例推导dp数组

斐波那契数

LeetCode题目：https://leetcode.cn/problems/fibonacci-number/

整体思路

按照五步进行分析，dp数组在本题目中的含义应该是数值i所具有的斐波那契数列。递推公式由斐波那契数的特性可得，dp[i] = dp[i-1] + dp[i-2]。对于斐波那契数，dp[1]和dp[0]的值是可以直接得到的，所以初始化前两个数值。

最后，根据递推公式可以执行正序的遍历。

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

爬楼梯

LeetCode题目：https://leetcode.cn/problems/min-cost-climbing-stairs/

解题思路

该题主要是对爬楼梯进行抽象。dp数组应当是对应到达第i个台阶所需要的方法。同时，由于可以爬一步或者两步，所以递推公式中能得到的到达第i个台阶由两个式子共同决定，即dp[i-1] + dp[i-2]。其中dp[i-1]其实可以理解为dp[i-2]使用两个一步的方法。

确定遍历方法，由于每个dp的条件应该由之前的条件确定，因此需要进行正序遍历。此外，为了保证i对应第i个台阶，所以应该dp初始化n+1个数值。

代码如下：

class Solution {
public:
    int climbStairs(int n) {
        if(n==1) return 1;
        vector<int> dp(n+1,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];
    }
};

使用最小花费爬楼梯

LeetCode题目：https://leetcode.cn/problems/climbing-stairs/

解题思路

该题主要是对爬楼梯进行抽象。dp数组应当是对应到达第i个台阶所需要的花费。同时，由于可以爬一步或者两步，所以递推公式中能得到的到达第i个台阶由两种花费的情况，即dp[i-1] + cost[i-1]和dp[i-2] + cost[i-2]。取得两者中的最小值即可。

确定遍历方法，由于每个dp的条件应该由之前的条件确定，因此需要进行正序遍历。此外，为了保证i对应第i个台阶，所以应该dp初始化n+1个数值。

代码如下：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        /* dp数组的含义：到达第i个台阶的最小花费 */
        /* 在第i个台阶向上到下一层时才花销第i个cost */
        vector<int> dp(n+1,0);
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2;i <= n;i++) {
            dp[i] = min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2]);
        }
        return dp[n];
    }
};

Foolish鱼