前几天做了小红薯的笔试题, 能感受到人家已经难度放水了, 奈何还是太菜最后一道没做出来, 于是痛定思痛, 总结一番

关键点:

寻找状态转移方程, 构造递推式, 将问题分解为若干子问题

本文持续更新中, 遇到新的题型就放进来!

线性动态规划

此类问题通常是与状态数组 / 矩阵相关, 例如经典的爬楼梯 / 打家劫舍.

爬楼梯

例题:
LeetCode. 70

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

分析:
我们可以使用递归的方法, 直接穷举出所有种数. 递归虽然直观, 但复杂度太高, 下面都将使用循环的方法解决.
我们只需要找出递推公式即可. 假设dp数组为 dp[n], 其中值代表种数
很明显, dp[n] = dp[n-1] + dp[n-2]
可见, 每次dp只用到了n和n-1, n-2这几个数, 因此我们可以用滚动数组的思想来优化.
优化后的源码如下

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

打家劫舍

例题:
LeetCode. 198

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

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

分析:
有了上面爬楼梯的分析, 同样, 我们只需找出递推式即可.
同样设dp[n], 值代表最大金额.
很明显, 要么偷当前的家, 跳过前一个; 要么不偷这家, 则最大值等于前一次.
因此, dp[n] = max(dp[n-1], dp[n-2] + value[n])

源码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int rob(vector<int> &nums) // optimized
{
    if (nums.size() <= 0)
        return 0;
    if (nums.size() == 1)
        return nums[0];
    int first = nums[0], second = max(nums[0], nums[1]);
    int res = second;
    for (int i = 2; i < nums.size(); i++) // 3+ house, dp
    {
        res = max(first + nums[i], second);
        first = second;
        second = res;
    }
    return res;
}

资源型动态规划

这类问题通常是在给定资源限定范围里, 获取最大的收益.

最经典的就是背包问题, 其他的资源型dp问题基本是背包问题的延伸.

背包问题

背包问题分为01背包, 完全背包, 多重背包(这个很少用到, 不用学)

01背包问题就是
有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

我们直接用8.6的小红薯试题为例. 题目如下

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
34
小红的分享日常
时间限制： 3000MS
内存限制： 589824KB
题目描述：
小红很喜欢前往小红书分享她的日常生活。已知她生活中有n个事件，分享第i个事件需要她花费ti的时间和hi的精力来编辑文章，并能获得ai的快乐值。

小红想知道，在总花费时间不超过T且总花费精力不超过H的前提下，小红最多可以获得多少快乐值？

输入描述
第一行输入一个正整数n，代表事件的数量。

第二行输入两个正整数T和H，代表时间限制和精力限制。

接下来的n行，每行输入三个正整数ti,hi,ai，代表分享第i个事件需要花费ti的时间、hi的精力，收获ai的快乐值。

1 ≤ n ≤ 50

1 ≤ T,H ≤ 500

1≤ ti,hi≤ 30

1≤ ai ≤ 109

输出描述
一个整数，代表小红最多的快乐值。

样例输入
3
5 4
1 2 2
2 1 3
4 1 5
样例输出
7

分析:
可见, 在传统背包问题上, 这题把原本的容量资源扩展到了二维:时间和精力. 价值仍不变.
因此, 我们同样先找递推式.
假设dp数组为 dp[i][t][h]. i代表前i个物品, t代表最大时间t范围. h代表最大精力.
因此, 我们分解子问题, 要找到i个物品范围内的最优解, 我们只需要判断
max((前i-1个, 不取第i个), (前i-1个, 取第i个))即可.
因此, 递推式为 max(dp[i-1][t][h], dp[i-1][t-ti][h-hi] + vi). 其中ti和hi为第i个物品的消耗. vi为第i个物品的价值.

此外, 众所周知可以用滚动数组的思想来优化.
但是需要注意
滚动数组优化时资源的遍历顺序需要倒过来

举个知乎的例子

1
2
3
4
5
6
7
8
// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 这个是为了展现dp数组里元素的变化
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

可以优化为

1
2
3
4
5
6
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

为什么中间那层需要反过来呢?
自己推导一下就很容易得知,
如果正序, 物品会被重复放入数组, 导致结果错误.
倒叙遍历是为了保证物品i只被放入一次.

因此, 小红薯这道题, 优化后的代码如下

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
int main()
{
    int n, t, h;
    cin >> n >> t >> h;
    //   int arr[n][3];  // time, effort, happiness
    event *arr = new event[n];
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i].time >> arr[i].effort >> arr[i].happiness;
    }

    vector<vector<int>> dp(t + 1, vector<int>(h + 1, 0));

    for (int item = 0; item < n; item++)
    {
        for (int time = t; time >= arr[item].time; time--)
        {
            for (int effort = h; effort >= arr[item].effort; effort--)
            {
                dp[time][effort] = max(dp[time][effort], dp[time - arr[item].time][effort - arr[item].effort] + arr[item].happiness);
            }
        }
    }
    cout << dp[t][h];
}

未完待续…..

参考文章
https://zhuanlan.zhihu.com/p/345364527