动态规划

核心：找状态定义和状态转移方程

启发：：由回溯选哪个/选或不选切入

打家劫舍

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

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

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

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
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        
        /*
        vector<int> cache(n,-1);		//剪枝
        auto dfs(this auto&& dfs, int i) ->int {
        	if(i < 0) return 0;
        	if(cache[i] != -1) return cache[i];
        	res = max(dfs(i-1), dfs(i-2) + nums[i]);
        	cache[i] = res;
        	return res;
        }
        */
        
        /*
        自顶向上 = 记忆化搜素 --》 自定向下 = 递推 {dfs -》数组，递归 -》循环，递归边界 -》数组初始值}
     	这样就有了状态转移：f[i] = max(f[i-1], f[i-2] + nums[i])
        */
        
        vector<int> f(n+2, 0);
        for(int i = 2; i < n + 2; ++i)
        {
            f[i] = max(f[i-1], f[i-2] + nums[i-2]
        }
        return f.back();
    }
};

dp模型

  • 至多装capacity，求方案数/最大价值和

  • 恰好装capacity，求方案数/最大/最小价值和

  • 至少装capacity，求方案数/最小价值和

0-1背包和完全背包

从n个物品选i个，每个物品至多选1次，求不超过体积的最大价值和

可以获得状态转移方程：

1
2
dfs(i,c) = max(dfs(i-1,c), dfs(i-1,c-w[i]) + v[i])
dfs(i,c) = dfs(i-1,c)+dfs(i-1,c-w[i])

例：493. 目标和

示例：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

咋一看好像跟上面三种方案没有关系，实际数组长度是5，元素都是1，可知（x -（sum-x））= target，通过转换就可以得到0-1背包的一种，即求恰好时的方案数，求x = （sum + target）/ 2

记忆化搜索可以1：1地翻译成递推

1
2
3
4
5
f[i][c] = f[i-1][c] + f[i-1][c-w[i]];
// 为了避免负数
f[i+1][c] = f[i][c] + f[i][c-w[i]];
//  当(target == 0 && i < 0)时 ,返回1
f[0][0] = 1;

倘若空间优化成一个数组

1
2
3
4
f[c] = f[c] + f[c-w[i]];
/*
这里从左→右计算，考虑到 f[c-w[j]]可能已经覆盖成f[i+1][c-w[i]]，而不是一开始的f[i][c-w[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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        target+=reduce(nums.begin(), nums.end());
        if(target<0 || target%2) return 0;
        target/=2;
        const int n = nums.size();

        vector<int> f(target+1);
        f[0] = 1;
        for(auto& x:nums)
        {
            for(int j = target; j>=x; j--)		// 优化：当j < x不选，即f[j]=f[j]，因此直接j>=x
                f[j] = f[j] + f[j-x];
        }
        return f[target];

        // vector<vector<int>> f(n+1,vector<int>(target+1));
        // f[0][0] = 1;
        // for(int i = 0; i < n; ++i)
        // {
        //     for(int j = 0;j < target+1; ++j)
        //     {
        //         if(j<nums[i]) f[i+1][j] = f[i][j];
        //         else f[i+1][j] = f[i][j]+f[i][j-nums[i]];
        //     }
        // }
        // return f[n][target];

        // vector cache(n, vector<int>(target+1, -1));
        // auto dfs = [&](this auto&& dfs, int i, int target) ->int {
        //     if(i < 0) return target == 0;
        //     int &res = cache[i][target];
        //     if(res != -1) return res;
        //     if(target < nums[i]) return res = dfs(i-1, target);
        //     return res = dfs(i-1, target) + dfs(i-1, target-nums[i]);
        // };
        // return dfs(n-1, target);
    }
};

完全背包：

从n种物品选i个，每个物品可以重复选，求不超过体积的最大价值和，同0-1背包，每次选完迭代依旧从i开始

例：322. 零钱兑换

1
2
3
4
f[i+1][c] = min(f[i][c], f[i+1][c-w[i]]+v[i])
// 优化空间
f[c] = min(f[c], f[c-w[i]]+v[i])
// 这时候就要从左→右计算了

[!NOTE]

总结一下上面空间的优化的两种情况：

  • 当f[c-w[i]]是f[i+1]的时，即我们需要往前获最新的元素，左👉右
  • 当f[c-w[i]]是f[i]的时，即我们需要往前获取之前的元素，左👈右

线性dp

最长公共子序列

比较两个最长公共子序列同样可以从选或不选出发，于是有:

dfs(n,m) = max( dfs(n-1, m), dfs(n, m-1), dfs(n-1, m-1) + s[n] == t[m]

  • 当s[n] == t[m] 时，考虑只选一个的递归，简单思考一个序列变短，一个不变，最长公共子序列只会小于等于原来的，所以只需要递归dfs(n-1)(m-1)
  • 当s[n] != t[m]时，那么dfs(n-1, m-1)已经包含在前两个递归里了，所以不需要递归dfs(n-1)(m-1)

最长递增子序列

dp时间复杂度进一步优化：交换状态与状态值 （二分+贪心）

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
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // int n = nums.size();
        // vector<int> f(n);
        // for(int i = 0; i < n; i++) {
        //     for(int j = 0; j < i; j++) {
        //         if(nums[j] < nums[i]) f[i] = max(f[i], f[j]);
        //     }
        //     f[i] += 1;
        // }
        // return *max_element(f.begin(), f.end());

        // vector<int> g;
        // for(int x:nums) {
        //     int j = ranges::lower_bound(g, x) - g.begin();
        //     if(j < g.size()) g[j] = x;
        //     else g.push_back(x);
        // }
        // return g.size();

        int ng = 0;
        for(int x:nums) {
            int j = lower_bound(nums.begin(), nums.begin()+ng, x) - nums.begin();
            if(j == ng) {
                nums[ng] = x;
                ng++;
            }
            else nums[j] = x;
        }
        return ng;
    }
};

状态dp

用bool来定义两个状态，即dfs(i, flag)是在第i天时有和没有的状态，这样就定义了状态，同时就拥有状态转移方程，边界条件是在第0天时的情况

1
2
dfs(i, 0) = max(dfs(i-1, 0), dfs(i-1, 1) + v[i])
dfs(i, 1) = max(dfs(i-1, 1), dfs(i-1, 0) - v[i])

区间dp

区别于线性dp的从前缀或后缀转移，区间dp从小区间转移到大区间，例如：1、从两侧向内转移；2、分割成更多规模子问题

例：1039. 多边形三角剖分的最低得分

寻找子问题：一个三角形将多边形分割成两个多边形，因此选定一条边，枚举顶点k得到状态转移方程：

1
dfs(i, j) = min( dfs(i, i+1) + dfs(i+1, j) + v, ... dfs(i, j-1) + dfs(j-1, j) + v )

树形dp

一、求树的直径（两个叶子节点到当前节点的链路）

因为是树，所以天然存在子问题，求每个子树的直径dfs(child) + 1，每次递归更新ans = max(ans, left + right)，返回子树最大直径

当变形求最大点权和时，同样模板，但是因为可能为负数，返回值为正数或者0

二、最大独立集

从图中选择尽量多的点，使得这些点互不相邻

变形：最大点权和

三、最小支配集

968. 监控二叉树

有三种状态，当前节点监控 = a，父节点监控 = b，孩子节点监控 = c，有转移方程

1
2
3
a = min(l_a, l_b) + min(r_a, r_b) + 1
b = min(l_a, l_c) + min(r_a, r_c)
c = b + max(0, min(l_a - l_c, r_a - r_c))

看到当为一般树，孩子节点监控的情况时，可以有a和c两种情况且必须有一个a，所以有2^n-1种情况，而b刚好覆盖2^n种情况，只需考虑当所有都是c的情况时，选一个最小的a即可（n为孩子节点个数）