算法动态规划

推公式优化DP

字数统计: 2.8k字   |   阅读时长: 13分
, ,

摘要: 一些可以通过推公式优化动态规划算法的问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

通过分析问题列出的动态规划的转移方程，有时经过一些公式推导后可以简化，这也是一种可以优化动态规划算法的思路。本文例举几个可以通过推公式优化动态规划的问题：

629. K个逆序对数组

逆序对的定义如下：对于数组 nums 的第 i 个和第 j 个元素，如果满足 0 <= i < j < nums.length 且 nums[i] > nums[j]，则其为一个逆序对；否则不是。

给你两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个 逆序对 的不同的数组的个数。由于答案可能很大，只需要返回对 1e9 + 7 取余的结果。

示例 1：
输入：n = 3, k = 0
输出：1
解释：
只有数组 [1,2,3] 包含了从1到3的整数并且正好拥有 0 个逆序对。

示例 2：
输入：n = 3, k = 1
输出：2
解释：
数组 [1,3,2] 和 [2,1,3] 都有 1 个逆序对。

提示：

1
2
1 <= n <= 1000
0 <= k <= 1000

算法：动态规划

1
2
3
4
5
6
7
8
状态定义:
dp[i][k] := [1..i] 恰好有 k 个逆序对的数组个数

初始化：
dp[i][0] = 0, dp[2][1] = 1

答案： 
dp[n][k]

考查 dp[i][j] 的转移：

  • 在 1,2,…,i-1 的末尾插入 i，不新增逆序对，转移到 dp[i-1][j]
  • 在 1,2,…,i-1 的中间插入 i，产生新逆序对，插入位置为 l，l 的范围 0,1,...,i-2对应 1,2,...,i-1 这 i - 1 个数。

于是转移方程如下：

1
2
dp[i][j] = dp[i - 1][j] + sum(dp[i - 1][j - ((i - 1) - l)]) 
其中： 0 <= l <= i - 2 且 j - (i - 1 - l) >= 0

代码 (C++)

注：$O(NKmin(N, K))$ 超时。

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 kInversePairs(int n, int k) {
        if(k == 0)
            return 1;
        if(n == 1)
            return 0;
        const int MOD = 1e9 + 7;
        using ll = long long;
        vector<vector<int>> dp(n + 1, vector<int>(k + 1));
        for(int i = 1; i <= n; ++i)
            dp[i][0] = 1;
        dp[2][1] = 1;
        for(int i = 3; i <= n; ++i)
            for(int j = 1; j <= k; ++j)
            {
                // 已有 1,2,...,i-1 排列，共 i-1 (0,1,...,i-2)
                dp[i][j] = dp[i - 1][j]; // 将 i 加在末尾
                for(int l = max(0, i - 1 - j); l <= i - 2; ++l)
                {
                    // 插入在 l (0, 1, ..., i - 2)
                    // 产生 (i - 1) - l 个
                    // j - ((i - 1) - l) > 0
                    dp[i][j] = (dp[i][j] + (ll)dp[i - 1][j - ((i - 1) - l)]) % MOD;
                }
            }
        return dp[n][k];
    }
};

推公式优化

考查 dp[i][j] 和 dp[i][j - 1]：

两式相减：

于是得到新的状态转移方程：

1
2
3
dp[i][j] = dp[i][j - 1] + dp[i-1][j]
if(j >= i)
    dp[i][j] -= dp[i-1][j-i]

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int kInversePairs(int n, int k) {
        if(k == 0)
            return 1;
        if(n == 1)
            return 0;
        const int MOD = 1e9 + 7;
        using ll = long long;
        vector<vector<int>> dp(n + 1, vector<int>(k + 1));
        for(int i = 1; i <= n; ++i)
            dp[i][0] = 1;
        dp[2][1] = 1;
        for(int i = 3; i <= n; ++i)
            for(int j = 1; j <= k; ++j)
            {
                dp[i][j] = (dp[i][j - 1] + (ll)dp[i - 1][j]) % MOD;
                if(j >= i)
                    dp[i][j] = ((ll)dp[i][j] - dp[i - 1][j - i] + MOD) % MOD;
            }
        return dp[n][k];
    }
};

1227. 飞机座位分配概率

有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。

剩下的乘客将会：

  • 如果他们自己的座位还空着，就坐到自己的座位上，
  • 当他们自己的座位被占用时，随机选择其他座位

第 n 位乘客坐在自己的座位上的概率是多少？

示例 1：
输入：n = 1
输出：1.00000
解释：第一个人只会坐在自己的位置上。

示例 2：
输入: n = 2
输出: 0.50000
解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。

提示：

1
1 <= n <= 10^5

算法：概率DP

事件: n 个人，n 个座位，第 1 个人随机选，后面 n - 1 个人按规则选，第 n 个人选的时候 n 未被占的概率。

概率: $p$

  1. 第一个乘客正确坐到第 1 个位置，为事件贡献概率为 $\frac{1}{n}$。
  2. 第一个乘客坐到第 n 位置，那么 n 将坐不对位置，为事件贡献概率 0。
  3. 第一个乘客坐到除了第 1 个和第 n 个以外的位置，为事件贡献概率 $p^{‘}$。

关键是这个 $p^{‘}$ 是什么：

若第 1 个选中了 j，1 < j < n，则 2,3,...,j-1 这些人都可以按规则坐自己的座位。

到第 j 个人时，因为 j 被 1 占了，按规则需要随机选择了，此时还剩 n - j + 1 个人，n - j + 1 个座位。

记 i = n - j + 1, 问题变成了:

i 个人，i 个座位，第 1 个人随机选，后面 i - 1 个人按规则选，第 i 个人选的时候 i 未被占的概率，记为 pi。(这里把第 1 个座位视为第 j 个人的票面座位。)

以上只是第 1 个人选 j 对 $p^{‘}$ 的贡献。将 j = 2,3,...,n-1 均带进去，其中 i = n - j + 1：

基于以上公式的动态规划：

1
2
3
4
5
6
7
8
9
10
11
状态定义：
dp[i] := i 个人，i 个座位，第 1 个人随机选，后面 i - 1 个人按规则选，第 i 个人选的时候 i 未被占的概率

初始化: 
dp[1] = 1, dp[2] = 0.5

答案：
dp[n]

状态转移：
dp[i] = 1/i + sum(dp[j]/i), j = 1,2,...,i-1

代码 (C++)

注: $O(N^{2})$ 超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    double nthPersonGetsNthSeat(int n) {
        if(n == 1) return 1;
        if(n == 2) return 0.5;
        vector<double> dp(n + 1, 0.0);
        dp[1] = 1.0;
        dp[2] = 0.5;
        for(int i = 3; i <= n; ++i)
        {
            dp[i] = 1 / (double)i;
            for(int j = 2; j < i; ++j)
                dp[i] = dp[i] + dp[j] / i;
        }
        return dp[n];
    }
};

推公式优化

考查 i >= 3 时的 dp[i] 和 dp[i-1]：

将上面两个式子相减得到：

最终得到：

代码 (C++)

1
2
3
4
5
6
7
8
class Solution {
public:
    double nthPersonGetsNthSeat(int n) {
        if(n == 1) 
            return 1;
        return 0.5;
    }
};

1621. 大小为 K 的不重叠线段的数目

给你一维空间的 n 个点，其中第 i 个点（编号从 0 到 n-1）位于 x = i 处，请你找到 恰好 k 个不重叠 线段且每个线段至少覆盖两个点的方案数。线段的两个端点必须都是 整数坐标 。这 k 个线段不需要全部覆盖全部 n 个点，且它们的端点 可以 重合。

请你返回 k 个不重叠线段的方案数。由于答案可能很大，请将结果对 1e9 + 7 取余 后返回。

提示：

1
2
2 <= n <= 1000
1 <= k <= n-1

示例 1：
输入：n = 4, k = 2
输出：5
解释：
如图所示，两个线段分别用红色和蓝色标出。
上图展示了 5 种不同的方案 {(0,2),(2,3)}，{(0,1),(1,3)}，{(0,1),(2,3)}，{(1,2),(2,3)}，{(0,1),(1,2)} 。

示例 2：
输入：n = 3, k = 1
输出：3
解释：总共有 3 种不同的方案 {(0,1)}, {(0,2)}, {(1,2)} 。

示例 3：
输入：n = 30, k = 7
输出：796297179
解释：画 7 条线段的总方案数为 3796297200 种。将这个数对 1e9 + 7 取余得到 796297179 。

示例 4：
输入：n = 5, k = 3
输出：7

示例 5：
输入：n = 3, k = 2
输出：1

算法：动态规划

1
2
3
4
5
6
7
8
dp[i][k] := i 个点取 k 条线的方案数
初始化
dp[k+1][k] = 1
dp[i][1] = i * (i - 1) / 2
答案
dp[n][K]
转移 (i > k + 1)
dp[i][k] = dp[i - 1][k] + sum(dp[i - l][k - 1]) 1 <= l <= i - k

代码 (C++)

$O(N^{3})$ 超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int numberOfSets(int n, int K) {
        if(n == K + 1) return 1;
        vector<vector<int>> dp(n + 1, vector<int>(K + 1));
        for(int k = 1; k <= K; ++k)
            dp[k + 1][k] = 1;
        for(int i = 2; i <= n; ++i)
            dp[i][1] = i * (i - 1) / 2;
        for(int k = 2; k <= K; ++k)
            for(int i = k + 2; i <= n; ++i)
            {
                dp[i][k] = dp[i - 1][k];
                for(int l = 1; l <= i - k; ++l)
                    dp[i][k] = (dp[i][k] + (ll)dp[i - l][k - 1]) % MOD;
            }
        return dp[n][K];
    }

private:
    using ll = long long;
    const int MOD = 1e9 + 7;
};

推公式优化

转移方程：

考察 $dp[i][k]$ 和 $dp[i-1][k]$：

展开写：

两式相减：

得到新的转移方程：

1
dp[i][k] = 2 * dp[i - 1][k] - dp[i - 2][k] + dp[i - 1][k - 1]

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int numberOfSets(int n, int K) {
        if(n == K + 1) return 1;
        vector<vector<ll>> dp(n + 1, vector<ll>(K + 1));
        for(int k = 1; k <= K; ++k)
            dp[k + 1][k] = 1;
        for(int i = 2; i <= n; ++i)
            dp[i][1] = i * (i - 1) / 2;
        for(int k = 2; k <= K; ++k)
            for(int i = k + 2; i <= n; ++i)
            {
                dp[i][k] = ((dp[i - 1][k] * 2 - dp[i - 2][k] + dp[i - 1][k - 1]) % MOD + MOD) % MOD;
            }
        return dp[n][K];
    }

private:
    using ll = long long;
    const int MOD = 1e9 + 7;
};

1639. 通过给定词典构造目标字符串的方案数

本题的内容和解答参考文章 【DP难题】力扣1639-通过给定词典构造目标字符串的方案。

Share