推公式优化DP

  |  

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

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


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


629. K个逆序对数组

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

给你两个整数 n 和 k,找出所有包含从 1 到 n 的数字,且恰好拥有 k 个 逆序对 的不同的数组的个数。由于答案可能很大,只需要返回对 109 + 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 个不重叠线段的方案数。由于答案可能很大,请将结果对 109 + 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 种。将这个数对 109 + 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