【Winter 2022 刷题】动态规划_综合

定义

将原问题拆成多个子问题，保留子问题的解
关键是找到状态转移方程

典型题

1. 依赖相邻（一维爬梯子，二维找路线）；依赖不相邻（分割）

542. 01 Matrix

找每个位置最近的0的距离：左上到右下走一遍，右下到左上走一遍

221. Maximal Square

由1构成的最大正方形：(i, j)记录以此为右下角的最大正方形边长；当(i, j)位置为1时，dp[i][j] = min(dp[i][j-1], dp[i-1][j-1], dp[i-1][j]) + 1
压缩空间：二维变一维，一维变变量

1143. Longest Common Subsequence

最长公共子序列：二维dp，字符相等dp[i][j] = dp[i-1][j-1] + 1，不相等dp[i][j] = max(dp[i][j-1], dp[i-1][j])

279. Perfect Squares

求正整数最少拆成几个平方数：dp[i] = min(dp[i], dp[i-j*j]) + 1

139. Word Break

输出是否可分割成可以在集合里找到的子串：dpbool vector记录此位置是否可以达到标准，如果substring在字符串里存在，则dp[i] = dp[i-len]

650. 2 Keys Keyboard

复制粘贴字符达到一定长度的最小次数：dp[j] + dp[i/j]

2. 背包问题（与sum有关）

N个物品，W容量，每个物品体积w价值v
0-1背包：只能选或不选；完全背包：不限定数量
思路：dp[i][j]表示前i件物品总价值不超过j的

// dp[N][W]即答案
// 通常N放外层
// 压缩空间至一维思路很简单，在此省略
for (int i = 1; i <= N; i++) {
    // N个物品，即weights和values长度均为Nint w = weights[i-1], v = values[i-1];for (int j = 1; j <= W; j++) {
    if (j >= w) {
    // 01背包dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);// 完全背包// dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v);// 自己这个物品可以被选多次所以时dp[i][j-w]，而不是01背包的dp[i-1][j-w]} else {
    dp[i][j] = dp[i-1][j]; // 一维数组实现时不需要这个}}
}

474. Ones and Zeroes

输出生成最多字符串的个数：三维01背包问题，需要同时考虑0和1的个数；dp[i][j] = max(dp[i][j], 1 + dp[i-count0][j-count1])

322. Coin Change

最小颗数组成指定金额：dp[i] = min(dp[i], dp[i-coin] + 1)；因为还需要记录是否可以达到，初始值可设为amount + 2（注意：初始值若设为INT_MAX会有overflow的风险）

3. 编辑与比较

72. Edit Distance

增删改字符串的最少操作次数：dp[i][j]表示字符串1的前i个字符的子串改成字符串2的前j个字符的子串的最少操作次数；初始值：i或j为0时代表空字符串，删除另一个字符串的所有字符即可，所以if (i == 0) dp[i][j] = i;；转移方程：相等 - dp[i-1][j-1]，删除 - dp[i-1][j] + 1，替换 - dp[i-1][j-1] + 1，插入 - dp[i][j-1] + 1

10. Regular Expression Matching

正则表达式匹配：分情况讨论；dp[i][j]表示字符串1的前i个字符的子串match字符串2的前j个字符

/* s - string - length: m (i)p - pattern - length: n (j) */// 初始值，false
dp[0][0] = true;// dp[0][j]，只有可能在有特定pattern的*的情况下有可能为true
for (int j = 2; j <= n; j++) {
     // dp[0][1]一定为falseif (p[j-1] == '*') {
    dp[0][j] = dp[0][j-2];}
}// dp[i][0]均为false，故不需要做任何操作// 主循环
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
    if (p[j-1] == '.') {
    // p第j个字符为'.'dp[i][j] = dp[i-1][j-1];} else if (p[j-1] != '*') {
    // p第j个字符为字母dp[i][j] = dp[i-1][j-1] && s[i-1] == p[j-1];} else if (p[j-2] != s[i-1] && p[j-2] != '.') {
    // p第j个字符为'*', p的前一个字符和s的第i个字符不matchdp[i][j] = dp[i][j-2]; // 跳过此'*'} else {
    // p第j个字符为'*', p的前一个字符和s的第i个字符match// dp[i][j-1]：可有可无// dp[i-1][j]：使用这个'*'dp[i][j] = dp[i][j-1] || dp[i-1][j] || dp[i][j-2];}}
}

4. 维护多数组

Best Time to Buy and Sell Stock IV

买卖股票k次最多同时拥有1支的最大利润：若k大于天数则随时维护两个数组，buy[j]表示第j次买入的最大收益；sell[j]表示第j次卖出的最大收益；若有cooldown，可以通过状态机推导转移方程

【Winter 2022 刷题】动态规划

定义

典型题