代码随想录算法训练营第38天 | 动态规划理论基础, 509.斐波那契数, 70.爬楼梯, 746.使用最小花费爬楼梯

动态规划理论基础

代码随想录链接

动态规划, 如果一个问题有很多重叠的子问题时, 最好的方法是使用动态规划. 动态规划的每个状态一定是由上一个状态推导出来, 区分与贪心算法, 贪心算法没有状态推导.

动态规划的解题步骤:

• 确定dp数组和下标的含义
• 确定递推公式
• dp数组的初始化
• 确定遍历数据
• 举例推导dp数组

509.斐波那契数

代码随想录链接

题目

LeetCode-509.斐波那契数

斐波那契数, 公式甚至直接给出来了.

自己的想法

根据给出的公式, 直接算就行.

解法

class Solution {
public:
    int fib(int n) {
        if (n < 2) return n;
        vector<int> nums(n + 1, 0);
        nums[1] = 1;
        for (int i = 2; i < nums.size(); i++)   // 递推所有数据, 直到F[n]
            nums[i] = nums[i - 1] + nums[i - 2];
        return nums[n];
    }
};

时间复杂度为\(O(n)\), 空间复杂度为\(O(1)\).

70.爬楼梯

代码随想录链接

题目

LeetCode-70.爬楼梯

有n阶台阶才能到达楼顶, 每次能上1或者2个台阶, 返回有多少种方法可以爬到楼顶.

自己的想法

每次都爬1或者2个台阶, 就是一个递推公式, 爬到第n个台阶的方法数是爬到第n-1层台阶和n-2层台阶的方法数之和. 故有\[F(n)=F(n-1)+F(n-2)\]

解法

class Solution {
public:
    int climbStairs(int n) {
        vector<int> nums(n);
        int dp[2];
        if (n == 1) return 1;
        dp[0] = 1;  // 初始化dp值
        dp[1] = 2;
        for (int i = 2; i < n; i++) {   // 根据递推公式计算值
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

时间复杂度为\(O(n)\), 空间复杂度为\(O(1)\).

746.使用最小花费爬楼梯

代码随想录链接

题目

LeetCode-746.使用最小花费爬楼梯

给定爬每个台阶的费用, 每支付一次费用可以往上爬一个或者两个台阶, 求爬到楼顶的最少花费.

自己的想法

递推公式也给出来了, 爬到第n个台阶的花费是\[F(n) = min((F(n-1) + cost[n-1]), (F(n-2)+cost[n-2]))\]

解法

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size() + 1, 0);
        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.back();
    }
};

时间复杂度为\(O(n)\), 空间复杂度为\(O(n)\).

还有另外一种写法: (此时的dp是指从开始到爬完当前位置的台阶需要多少花费)好奇怪的想法

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