本文共 5732 字，大约阅读时间需要 19 分钟。

LeetCode学习笔记：动态规划入门

第一天

LeetCode509.斐波拉契数

斐波拉契数列是一个简单但经典的数列问题。最初的几次思考和尝试可能会迷惘你，但当你理清递归关系后，动态规划的方法成为解决这个问题的标准做法。

解决思路

斐波拉契数列定义为：F(n) = F(n-1) + F(n-2)，F(1) = 1，F(2) = 1。递归方法可能会因为重复计算而效率低下，因此可以通过动态规划来优化。

解决代码

#include 
   
    class Solution {public:    int fib(int N) {        if (N <= 1) {            return N;        }        std::vector
    
      dp(N + 1, 0);        dp[0] = 0;        dp[1] = 1;        for (int i = 2; i <= N; ++i) {            dp[i] = dp[i - 1] + dp[i - 2];        }        return dp[N];    }};
    
   

LeetCode1137.第N个泰波那契数

泰波那契数列类似于斐波拉契数，但它涉及三个前项的和。对于这个问题，可以使用动态规划来高效解决。

解决思路

泰波那契数列的第n项可以表示为T(n) = T(n-1) + T(n-2) + T(n-3)。我们可以通过动态规划来存储各个项的值，避免重复计算。

解决代码

class Solution {public:    int tribonacci(int n) {        int dp[38] = {0}; // 足够覆盖n的范围        dp[0] = 0;        dp[1] = 1;        dp[2] = 1;        if (n <= 2) {            return dp[n];        }        for (int i = 3; i <= n; ++i) {            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];        }        return dp[n];    }};

第二天

LeetCode70.爬楼梯

这个题目是一个经典的动态规划问题，常出现在Excel或剑指offer中。

解决思路

爬楼梯问题可以通过动态规划来解决。我们假设dp[i]表示爬到第i个台阶所需的最小排斧数。对于每个台阶i，我们可以选择从i-1或i-2台阶爬上来。

解决代码

#include 
   
    class Solution {public:    int climbStairs(int n) {        if (n <= 2) {            return n;        }        std::vector
    
      dp(n + 1, 0);        dp[1] = 1;        dp[2] = 2;        for (int i = 3; i <= n; ++i) {            dp[i] = dp[i - 1] + dp[i - 2];        }        return dp[n];    }};
    
   

LeetCode746.最小花费爬楼梯

这个问题比爬楼梯稍复杂，我们需要找到最优路径花费最少。

解决思路

在爬楼梯问题中，每次可以选择爬1步或2步，我们需要选择花费最小的方式。因此，我们可以用动态规划来记录每一步的最小花费。

解决代码

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

第三天

LeetCode198.打家劫舍

这是一个经典的动态规划问题，经常出现在面试中。假设房子处于一条直线上，偷盗的规则是不能偷相邻的房子。

解决思路

假设dp[i]表示偷到第i个房子的最大值。当偷第i个房子时，偷前的房子必须是i-2；如果不偷第i个房子，那么最大值可能来自i-1或i-2。这两种情况的最大值决定了dp[i]的值。

解决代码

class Solution {public:    int rob(const std::vector
   
    & nums) {        if (nums.empty()) {            return 0;        } else if (nums.size() == 1) {            return nums[0];        }        int dp1[nums.size()];        int dp2[nums.size()];        dp1[0] = nums[0];        dp1[1] = std::max(nums[0], nums[1]);        for (int i = 2; i < nums.size() - 1; ++i) {            dp1[i] = std::max(dp1[i - 1], dp1[i - 2] + nums[i]);        }        dp2[0] = 0;        dp2[1] = nums[1];        for (int i = 2; i < nums.size(); ++i) {            dp2[i] = std::max(dp2[i - 1], dp2[i - 2] + nums[i]);        }        return std::max(dp1[nums.size() - 2], dp2[nums.size() - 1]);    }};
   

LeetCode213.打家劫舍II

这个问题的复杂之处在于有环。这时，我们需要考虑两种情况：一种是偷第一个房子，一种是不偷第一个房子。

解决思路

我们用动态规划分别处理这两种情况。如果偷了第一个房子，那么最后一个房子不能偷；如果不偷第一个房子，那么可以偷最后一个房子。最后取其中的最大值。

解决代码

class Solution {public:    int rob(const std::vector
   
    & nums) {        int N = nums.size();        if (N == 0) {            return 0;        }        int dp1[N];        int dp2[N];        dp1[0] = nums[0];        dp1[1] = std::max(nums[0], nums[1]);        for (int i = 2; i < N - 1; ++i) {            dp1[i] = std::max(                dp1[i - 1],                dp1[i - 2] + nums[i]            );        }        dp2[0] = 0;        dp2[1] = nums[1];        for (int i = 2; i < N; ++i) {            dp2[i] = std::max(                dp2[i - 1],                dp2[i - 2] + nums[i]            );        }        return std::max(dp1[N - 2], dp2[N - 1]);    }};
   

LeetCode740.删除无法获得点数的房子

我们需要删除无法从相邻房子中获得点数的房子。这正是经典的打家劫舍问题，只是房子被独立处理，而不是放在一条直线上。

解决思路

构造一个间隔数组，每个元素的值等于本身数与其索引的和。然后用动态规划的方法来解决这个问题。

解决代码

#include 
   
    class Solution {public:    int deleteAndEarn(const std::vector
    
     & nums) {        std::vector
     
       temp(10001, 0);        for (int num : nums) {            temp[num] += num;        }        std::vector
      
        dp(10001, 0);        dp[0] = 0;        dp[1] = temp[1];        for (int i = 2; i < 10001; ++i) {            dp[i] = std::max(                dp[i - 2] + temp[i],                dp[i - 1]            );        }        return dp[10000];    }};
      
     
    
   

第四天

LeetCode55.跳跃游戏

这个问题可以通过贪心算法来解决。在代码中，我们只需要跟踪当前能跳到的最远点，同时更新最远跳跃点。

解决思路

在每一步，更新当前能跳到的最大点，同时记录一旦超过等于数组长度，那么就说明可以达到终点。

解决代码

#include 
   
    class Solution {public:    bool canJump(const std::vector
    
     & nums) {        int maxDis = nums[0];        for (int i = 1; i < nums.size(); ++i) {            if (i <= maxDis) {                maxDis = std::max(maxDis, nums[i] + i);            }        }        return maxDis >= nums.size() - 1;    }};
    
   

LeetCode45.跳跃游戏II

这个问题比跳跃游戏复杂，因为我们需要找出到达终点的最多跳跃次数。可以使用动态规划来记录每个点的最远能跳跃距离。

解决思路

dp[i]表示从第i个点出发，能跳到的最远点。我们通过遍历数组，更新每个点的最远跳跃距离。

解决代码

#include 
   
    class Solution {public:    int jumpGameII(const std::vector
    
     & nums) {        int n = nums.size();        if (n == 0) {            return 0;        }        std::vector
     
       dp(n, 0);        dp[0] = nums[0];        for (int i = 0; i < n; ++i) {            if (dp[i] == 0) {                continue;            }            int reach = std::max(i + nums[i], n - 1);            if (reach >= n) {                return n - 1;            }            if (dp[reach] < nums[reach]) {                dp[reach] = nums[reach];            }        }        return dp[n - 1];    }};
     
    
   

总结

这些问题展示了动态规划在不同场景下的应用。从斐波拉契数和泰波那契数的计算，到爬楼梯、打家劫舍、跳跃游戏等，这些经典问题都可以通过动态规划高效解决。通过这些练习，你可以逐渐掌握动态规划的思维方式，为后续的算法题打下坚实的基础。