动态规划基础

动态规划基础

动态规划类型的题目可以分为四步

• 定义子问题
• 写出子问题的递推关系
• 确定DP数组的计算顺序
• 空间优化（可以优化，可以不优化）

接下来我们使用力扣的几个例子来看一下动态规划问题：

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

接下来我们按照动态规划的四步骤来

• 第一步：定义子问题

  我们可以把n阶的阶梯的总数分解为k阶阶梯的数量来计算

• 第二步：写出子问题的递推关系

  f(x) = f(x-1)+f(x-2)的关系

• 第三步：确定数组的计算顺序

• 第四步：空间优化

class Solution
{
public:
    int climbStairs(int n)
    {
        if (n <= 2)
        {
            return n;
        }
        int dp[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++)
        {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
        // 使用滚动数组的方式来优化计算空间
        int k = 1, q = 2, ret = 3;
        for (int i = 3; i < n; i++)
        {
            k = q;
            q = ret;
            ret = k + q;
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

509. 斐波那契数

该问题，给定n计算F(n)

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
1
2

该问题直接把公式给了我们，则第一步定义子问题和第二步的递推关系已经不需要我们考虑了，接下来我们只要做后续的操作即可

class Solution {
public:
    int fib(int n) 
    {
        if(n < 2)
        {
            return n;
        }

        int dp[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
		// 使用滚动数组的方式来优化计算空间
        int p = 0, q = 0, r = 1;
        for (int i= 2; i <= n; ++i)
        {
            p =  q;
            q= r;
            r = p + q;
        }
        return r;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

该问题直接把公式给了我们，则第一步定义子问题和第二步的递推关系已经不需要我们考虑了，接下来我们只要做后续的操作即可

class Solution {
public:
    int tribonacci(int n) 
    {
        if (n == 0)
        {
            return 0;
        }
        if (n == 1 || n == 2)
        {
            return 1;
        }
        int dp[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++)
        {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        return dp[n];
		// 使用滚动数组的方式来优化计算空间
        int p = 0, q = 1, r = 1 , m = 2;
        for (int i = 3; i < n; i++)
        {
            p = q;
            q = r;
            r = m;
            m = p+q+r;
        }
        return m;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

746. 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费

该题目需要分析一下

• 第一步：可不可以分解为子问题，可以分解为爬k个楼梯
• 第二步：可以找到对应的递推关系吗？dp[0]=dp[1]=0。 dp[n] = min(dp[i-1]+cost[i-1] + dp[i-2]+cost[i-2])

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        int n = cost.size();
        vector<int> dp(n + 1);
        dp[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];
        // 使用滚动数组的方式来优化计算空间
        int prev = 0, curr = 0;
        for (int i = 2; i <= n; i++) {
            int next = min(curr + cost[i - 1], prev + cost[i - 2]);
            prev = curr;
            curr = next;
        }
        return curr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

​ // 子问题 偷0-k房间中的最大金额

​ // f0 = 0 f1 = nums[0] fk = max{ rob(k-1), nums[k-1] + robs(k-2) }

class Solution {
public:
    int rob(vector<int>& nums) 
    {
        int n = nums.size();
        if (n == 0)
        {
            return 0;
        }
        vector<int> dp(n+1, 0);
        dp[0] = 0;
        dp[1] = nums[0];
        for (int k = 2; k <= n; k++)
        {
            dp[k] = max(dp[k-1], nums[k-1] + dp[k-2]);
        }
        return dp[n];
        // 使用滚动数组的方式来优化计算空间
        int first = 0, curr = nums[0];
        for (int k = 2; k <= n; k++)
        {
            int next = max(curr, nums[k-1] + first);
            first = curr;
            curr = next;
        }
        return curr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

740. 删除并获得点数

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

该题目是打家劫舍的翻版，只要将数组转换成一个下标从0到maxVal[nums[i]]的数组，且每个下标对应的数字是num[i]的个数*num即可

class Solution {
public:
    int rob(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> dp(n+1, 0);
        dp[0] = 0;
        dp[1] = nums[0];

        for (int k = 2; k <= n; k++)
        {
            dp[k] = max(dp[k-1], nums[k-1] + dp[k-2]);
        }
        return dp[n];
    }

    int deleteAndEarn(vector<int>& nums) 
    {
        int maxVal = *std::max_element(nums.begin(), nums.end());

        vector<int> sum(maxVal+1, 0);
        
        for (int val : nums) 
        {
            sum[val] += val;
        }
        
        return rob(sum);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30