算法动态规划

单串线性DP-多维状态,在阶段的基础上附加维度

字数统计: 2.1k字   |   阅读时长: 10分
,

求解 DP 问题时，一般需要先确定阶段。如果阶段不足以表示一个状态，可以把所需的附加信息也作为状态的维度。

对于单串线性 DP 的问题，i 是单串 s 上的位置，作为阶段，具有时间或者位置等含义。有时只有单串上的位置不足以表示状态，需要同时附加一个维度 k，一般 k 会有长度，个数，次数，颜色等含义。

当出现附加维度在转移时没有固定方向的情况，有时候 k 的取值范围事先也不清楚，可以用记忆化搜索处理。

当 k 有一定的转移规则时，有时可以用自动机简化代码。

801. 使序列递增的最小交换次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
swap[i] := A[i], B[i] 交换时，[0..i] 的最小步数
keep[i] := A[i], B[i] 保持时，[0..i] 的最小步数

答案
min(swap[n - 1], keep[n - 1])

初始化
keep[0] = 0
swap[0] = 1

转移
A[i - 1] < A[i], B[i - 1] < B[i]: 
    keep[i] = keep[i - 1]
    swap[i] = swap[i - 1] + 1

A[i - 1] < B[i], B[i - 1] < A[i]: 
    swap[i] = min(swap[i], keep[i - 1] + 1)
    keep[i] = min(keep[i], swap[i - 1])

以上 DP 状态的定义等于是在 i 的基础上多了一个表示最后一步是交换还是保持的状态，即 dp[i][k] 其中 k = {0, 1}

1187. 使数组严格递增

1
dp[i][k] := 当上一步操作为 k 时，使得 [i..n-1] 递增所需步数

注: k 这一维没有固定方向的转移，因此用记忆化搜索

873. 最长的斐波那契子序列的长度

1
2
3
4
5
6
7
8
9
10
11
12
dp[i][k]:= 考虑 arr[0..i] 且以 i 结尾，且上一个位置为 k 时的斐波那契子序列最大长度

初始化
dp[...][0] = 0
dp[0][...] = dp[1][...] = 0

答案
max(dp[i][k])

转移
dp[i][k] = max(3, dp[k][j] + 1)
其中 a[j] + a[k] = a[i]

注：可以用哈希表优化转移

1027. 最长等差数列

1
2
3
4
dp[i][k]:= 考虑 arr[0..i] 且以 i 结尾，且上一个位置为 k 时的斐波那契子序列最大长度

dp[i][k] = max(dp[k][j] + 1)
其中 0 <= j < k 且 A[j] = A[k] - (A[i] - A[k])

注：可以用哈希表优化转移

813. 最大平均值和的分组

1
2
3
4
dp[i][k] = [i..n-1] 上分 k 组可以取到的最大值

dp[i][k] = max(dp[j][k - 1] + (sums[j] - sums[i]) / (j - i))
其中 i < j < n

887. 鸡蛋掉落

1
2
3
4
dp[i][k] := i 个鸡蛋, 需要测试 k 层楼时的最少次数

dp[i][k] = min(max(dp[i - 1][j - 1], dp[i][k - j]))
其中 1 <= j <= k

注：可以用决策单调性优化

256. 粉刷房子

1
2
3
4
5
dp[i][k] := [0..i] 上，第 i 个房子染 k 色时的最低成本

dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0]
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1]
dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2]

265. 粉刷房子 II

1
2
3
4
dp[i][k] := [0..i] 上，第 i 个房子染 k 色时的最低成本

dp[i][k] = min(dp[i - 1][j]) + costs[i][k]
其中 j != k

注：在求 i - 1 阶段时，可以顺便保存 dp[i - 1][j] 的最小值，次小值。在本阶段计算时可以不用遍历上一阶段的结果了。

975. 奇偶跳

1
2
3
4
5
6
7
8
9
10
dp[i][k] := 当前在位置 i，下一跳的状态为 k 时，能否到最右, k = {0, 1}
0: 偶跳，1：奇跳

初始化
dp[n - 1][0] = true
dp[n - 1][1] = true

转移
dp[i][0] := dp[j][1], j 为使得 A[i] >= A[j] 的最大 A[j] 的最小 j
dp[i][1] := dp[j][0], j 为使得 A[i] <= A[j] 的最小 A[j] 的最小 j

注：j 的查询可以用平衡树优化

403. 青蛙过河

1
2
3
4
5
dp[i][k] := 当前在位置 i，上一步的位置为 k，能否跳到 x

转移
当 j == x，dp[i][k] = true
当 j > x 且 j 为石子， dp[i][k] = dp[i + j][j]

注：k 没有固定的转移方向，用记忆化搜索

1478. 安排邮筒

1
2
3
4
dp[i][k] = 分为 i 段，考虑 [0..k] 的最小 cost

dp[i][k] = min(dp[i - 1][j] + cost(j + 1, k))
其中 j < k

注：可以用决策单调性优化

1230. 抛掷硬币

1
2
3
dp[i][k] := 考虑到 i，有 k 个正面的概率

dp[i][k] = prob[i] * dp[i - 1][k - 1] + (1 - prob[i])dp[i - 1][k]

注：概率DP

410. 分割数组的最大值

1
2
3
dp[i][k] := [i..n-1] 分割为 k 份的答案(各个段和中最大值的最小值)

dp[i][k] = min(dp[i][k], max(dp[j][k - 1], sums[i] - sums[j]));   0 <= j < i

力扣410-分割数组的最大值

1473. 给房子涂色 III

1
dp[i][k][t] := [0..i] 上，第 i 个涂 k 色，共 t 个街区的涂法

注：k 和 t 转移规则太乱，用记忆化搜索

446. 等差数列划分 II - 子序列

1
2
3
dp[i][k] := 考虑 A[0..i] 且以 i 结尾，公差为 k 的子序列个数

dp[i][A[i] - A[j]] = sum(dp[j][A[i] - A[j]] + 1)

903. DI 序列的有效排列

1
2
3
4
5
dp[i][k] := [0..i] 上, p[i] = k 时，合法 p[0..i] 的数量
dp[0][0] =1

dp[i][j] = sum(dp[i-1][k]) j <= k <= i-1 s[i-1]='D'
         = sum(dp[i-1][k]) 0 <= k <= j-1 s[i-1]='I'

983. 最低票价

1
2
dp[i][k] := 考虑 [0..i] 的最少花费, k = {0,1,2,3}
0: 不买, 1: 买 1 天, 2: 买 7 天, 3: 买 30 天
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
class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int n = days.size();
        vector<vector<int>> dp(n, vector<int>(4, INT_MAX));
        dp[0][1] = costs[0], dp[0][2] = costs[1], dp[0][3] = costs[2];
        for(int i = 1; i < n; ++i)
        {
            int minx = dp[i - 1][0];
            for(int k = 1; k < 4; ++k)
                minx = min(minx, dp[i - 1][k]);
            dp[i][1] = minx + costs[0];
            dp[i][2] = minx + costs[1];
            dp[i][3] = minx + costs[2];
            if(days[i] >= days[i - 1] + 30) // dp[i][0] = INF
                continue;
            // days[i] < days[i - 1] + 30
            // dp[i][0] 可能被前面的 30 覆盖
            for(int j = i - 1; j >= 0 && days[j] + 30 > days[i]; --j)
                dp[i][0] = min(dp[i][0], dp[j][3]);
            // dp[i][0] 可能还有可能被前面的 7 覆盖
            for(int j = i - 1; j >= 0 && days[j] + 7 > days[i]; --j)
                dp[i][0] = min(dp[i][0], dp[j][2]);
        }
        int ans = dp[n - 1][0];
        for(int k = 1; k < 4; ++k)
            ans = min(ans, dp[n - 1][k]);
        return ans;
    }
};

487. 最大连续1的个数 II

1
2
dp[i] := 考虑到 i 的最大连续 1 的个数 k = {0, 1}
0: 未使用操作，1: 已使用操作

956. 最高的广告牌

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
dp[i][s] := [0...i] 中，当组成的左右高度差为 s 时，左右的最大公共高度

转移：
(1) rods[i] 用，且放在较高一侧
dp[i][s + rods[i]] = max(dp[i][s + rods[i]], dp[i - 1][s]);
(2) rods[i] 用，且放在较矮一侧
dp[i][abs(s - rods[i])] = max(dp[i][abs(s - rods[i])], dp[i - 1][s] + min(s, rods[i]));
(3) rods[i] 不用
dp[i][s] = max(dp[i][s], dp[i - 1][s]);

初始化
dp[i][s] = -INF
dp[0][0] = 0

答案
dp[n][0]

【搜索难题】力扣956-最高的广告牌

1278. 分割回文串 III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
预处理
dp1[i][j] := [i..j] 变为回文串的最少修改次数
全初始化为 0
dp1[i][j] = dp[i + 1][j - 1] + 1  s[i] != s[j]
            dp[i + 1][j - 1]      s[i] == s[j]

线性 DP，阶段 + 附加状态
dp2[i][k] := [0..i] 分 k 个，最少的修改次数

转移
i + 1 >= k
dp2[0][1] = 0
dp2[i][k] = min{
     dp1[0][i]                            k == 1
     dp2[j - 1][k - 1] + dp1[j][i]    k > 1 && 0 < j <= i
                                      && j - 1 + 1 >= k - 1
}
Share