LeetCode刷题笔记【29】：动态规划专题-1（斐波那契数、爬楼梯、使用最小花费爬楼梯）

前置知识

解题思路

动态规划（DP，Dynamic Programming）。
其解题思路对比贪心算法的“直接选局部最优然后推导出全局最优”；倾向于“由之前的结果推导得到后续的结果”。
很多时候二者具有相似性，不必死扣概念。

解题步骤

动态规划题目的核心是dp数组的概念和构建(递推公式);
所以具体的解题步骤可以分为以下几步:

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

动态规划的debug

每走一步都将dp数组打印出来, 检查是否和自己推导和计划的一致.

当出现bug的时候, 思考:

• 这道题目我举例推导状态转移公式了么？
• 我打印dp数组的日志了么？
• 打印出来了dp数组和我想的一样么？

参考文章：动态规划理论基础

509. 斐波那契数

题目描述

LeetCode链接：https://leetcode.cn/problems/fibonacci-number/description/

解题思路

因为是简单题, 所以直接给出了递推公式, 我们只需要先构建dp数组的前两项, 然后依次向后传递推导即可.

代码

使用dp数组

class Solution {
public:
    int fib(int n) {
        vector<int> fei;
        fei.push_back(0);
        fei.push_back(1);
        for(int i=2; i<=n; ++i){
            fei.push_back(fei[i-1] + fei[i-2]);
        }
        return fei[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

优化空间复杂度: 不用数组, 只用两个变量记录即可

class Solution {
public:
    int fib(int n) {
        if(n==0)    return 0;
        else if(n==1)   return 1;
        int first=0, second=1;
        for(int i=2; i<=n; ++i){
            int tmp = first + second;
            first = second;
            second = tmp;
        }
        return second;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

70. 爬楼梯

题目描述

LeetCode链接：https://leetcode.cn/problems/climbing-stairs/description/

解题思路

本质上和前一题的斐波那契数列是一样的.

发现第i阶的可能性, 是i-1阶和i-2阶的和
可以理解为: 从i-1阶和i-2阶都可以直接到达i阶, 所以dp[i]=dp[i-1]+dp[i-2]

代码

使用dp数组

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp;
        dp.push_back(1);
        dp.push_back(1);
        for(int i=2; i<=n; i++){
            dp.push_back(dp[i-1] + dp[i-2]);
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

优化空间复杂度: 不用数组, 只用两个变量记录即可

class Solution {
public:
    int climbStairs(int n) {
        if(n==0 || n==1)    return 1;
        int first=1, second=1;
        for(int i=2; i<=n; i++){
            int tmp = first+second;
            first = second;
            second = tmp;
        }
        return second;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

746. 使用最小花费爬楼梯

题目描述

LeetCode链接：https://leetcode.cn/problems/min-cost-climbing-stairs/description/

解题思路

思路: 动态规划
dp[i] 表示从i处起跳的话, 需要支付的费用
那么就有: dp[i] = min(dp[i-1], dp[i-2]) + cost[i];

代码

使用dp数组

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        vector<int> dp(n);
        dp[0] = cost[0];
        dp[1] = cost[1];
        for(int i=2; i<n; ++i){
            dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
        }
        return min(dp[n-1], dp[n-2]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

优化空间复杂度

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        int first = cost[0];
        int second = cost[1];
        for(int i=2; i<n; ++i){
            int tmp = min(first, second) + cost[i];
            first = second;
            second = tmp;
        }
        return min(first, second);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

另一种动态规划思路

用另一种思路来构建dp数组:
刚才认为"dp[i]是从i处起跳需要支付的代价", 现在认为"dp[i]是到达i需要支付的代价"
递推公式也就变为: dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);

所以最开始的dp[0]和dp[1]初始化为0, dp的长度也设置为cost.size()+1, 一路推导到dp[cost.size()], 直接return即可

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        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()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

总结

本文参考：
斐波那契数
爬楼梯
使用最小花费爬楼梯