动态规划感悟1

下面的感悟主要还是基于力扣上面动态规划（基础版）得出来的相关的做题结论

动态规划（基础版） - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台

首先是

斐波那契类型的动态规划
70. 爬楼梯 - 力扣（LeetCode）

主要的方法就是需要知道下面的公式
$$f(x)=f(x-1)+f(x-2)$$
也就是说爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。然后就是确定边界条件：我们是从第 0 级开始爬的，所以从第 0 级爬到第 0 级我们可以看作只有一种方案，即 f(0)=1；从第 0 级到第 1 级也只有一种方案，即爬一级，f(1)=1。

后面的快速矩阵幂和公式法可以看官方的题解

// 这段代码的时间复杂度是最低的
class Solution
{
public:
    int climbStairs(int n)
    {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < n + 1; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
};
// 时间复杂度比较的高，空间复杂度还是比上面的代码好一点
class Solution
{
public:
    int climbStairs(int n)
    {
        int a = 1, b = 1, temp;
        for (int i = 1; i < n; i++)
        {
            temp = a;
            a = b;
            b = b + temp;
        }
        return b;
    }
};复制

509. 斐波那契数 - 力扣（LeetCode）

和爬楼梯是一样的解法

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

1137. 第 N 个泰波那契数 - 力扣（LeetCode）

是上面两道题目的变体，需要确定如下的递推关系：
$$T(n)=T(n-1)+T(n-2)+T(n-3)$$

class Solution
{
public:
    int tribonacci(int n)
    {
        if (n == 0)
            return 0;
        if (n == 1 || n == 2)
            return 1;
        vector<int> dp(n + 1, 0);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i < n + 1; i++)
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        return dp[n];
    }
};复制

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

要想使用动态规划，主要是需要确定好状态转移方程。不妨以dp[i]表示达到下标i的最小花费。

则dp[0]=dp[1]=0,这是边界条件。

当 2≤i≤n 时，可以从下标 i−1 使用 cost[i−1] 的花费达到下标 i，或者从下标 i−2 使用 cost[i−2] 的花费达到下标 i。为了使总花费最小，dp[i] 应取上述两项的最小值，因此状态转移方程如下：

$$dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])$$
然后在进行计算，可以最终求出来dp[n]的最小花费出来。

当然，注意到当 i≥2 时，dp[i] 只和 dp[i−1] 与 dp[i−2] 有关，因此可以使用滚动数组的思想，将空间复杂度优化到 O(1)。

// 时间复杂度和空间复杂度都是O(n)
class Solution
{
public:
    int minCostClimbingStairs(vector<int> &cost)
    {
        int length = cost.size();
        if (length == 0)
            return 0;
        if (length == 1)
            return cost[0];
        if (length == 2)
            return min(cost[0], cost[1]);
        vector<int> dp(length + 1, 0);
        for (int i = 2; i < length + 1; i++)
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        return dp[length];
    }
};
 
// 使用滚动数组
class Solution
{
public:
    int minCostClimbingStairs(vector<int> &cost)
    {
        int n = cost.size();
        int prev = 0, curr = 0; // prev代表指向curr的前一个位置
        for (int i = 2; i <= n; i++)
        {
            int next = min(curr + cost[i - 1], prev + cost[i - 2]);
            prev = curr;
            curr = next;
        }
        return curr;
    }
};复制

198. 打家劫舍 - 力扣（LeetCode）

用dp[i]表示前i间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：
$$dp[i]=max(dp[i-2]+nums[i],dp[i-1])$$
边界条件为：
$$\{\begin{array}{llcc}dp[0]& =nums[0]& & \text{只有一间房屋，则偷窃该房屋}\\ dp[1]& =\max (nums[0],nums[1])& & \text{只有两间房屋，选择其中金额较高的房屋进行偷窃}\end{array}$$

// 比较的复杂，但是能够通过
class Solution
{
public:
    int rob(vector<int> &nums)
    {
        int length = nums.size();
        if (length == 0)
            return 0;
        if (length == 1)
            return nums[0];
        if (length == 2)
            return max(nums[0], nums[1]);
        if (length == 3)
            return max(nums[0] + nums[2], nums[1]);
        nums[2] = nums[2] + nums[0];
        int maxm = nums[2];
        for (int i = 3; i < length; i++)
        {
            nums[i] += max(nums[i - 2], nums[i - 3]);
            maxm = max(maxm, nums[i]);
        }
        return maxm;
    }
};
 
// 下面的方法是比较的好的
class Solution
{
public:
    int rob(vector<int> &nums)
    {
        int length = nums.size(); // 用来记录数组的长度
        if (length == 0)
            return 0;
        if (length == 1)
            return nums[0];
        nums[1] = max(nums[0], nums[1]); // nums[1]用来记录的是前2间房子能够获得的最大金额
        for (int i = 2; i < length; i++)
            nums[i] = max(nums[i - 2] + nums[i], nums[i - 1]);
        return nums[length - 1];
    }
};
 
// 当然，也是可以使用滚动数组进行求解的。
class Solution {
public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        if (len == 0)
            return 0;
        if (len == 1)
            return nums[0];
        nums[1] = max(nums[0], nums[1]);
        int first = nums[0], second = nums[1]; // first始终指向second左侧
        for (int i = 2; i < len; i++) {
            int temp = max(nums[i] + first, second);
            first = second;
            second = temp;
        }
        return second;
    }
};复制