九章算法笔记D6-区间型动态规划

@[toc]

D6 区间型动态规划

类型

  1. 给定一个序列/字符串,进行一些操作
  2. 最后一步会将序列/字符串去头/去尾
  3. 剩下的会是一个区间[i,j]
  4. 状态自然定义为f[i][j],表示面对子序列[i,...,j] 时的最优性质
  5. 千万不能按照i的顺序去算!按照长度从小到大去算
1
2
3
4
for(int l=2;l<=n;l++)
for(int i=1,j=i+l-1;j<=n;i++,j++)
for(int k=i;k<j;k++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);

最长回文子序列

描述

给一字符串 s, 找出在 s 中的最长回文子序列的长度. 你可以假设 s 的最大长度为 1000.

样例1

1
2
3
输入: "bbbab"
输出: 4
解释:一个可能的最长回文序列为 "bbbb"

分析

转移方程:f[i][j]S[i...j]的最长回文子串的长度

f[i][j] = max{f[i+1][j],f[i][j-1],f[i+1][j-1]+2|S[i]=S[j]}

  • S[i..j] 的最长回文子串的长度
  • S[i+1…j] 的最长回文子串的长度
  • S[i…j-1] 的最长回文子串的长度
  • S[i+1…j-1] 的最长回文子串的长度,此时S[i]=S[j],所以长度+2

初始条件

  • f[0][0]=f[1][1]=...=f[N-1][N-1]=1
  • 如果S[i] ==S[i+1],f[i][i+1]==2
  • 如果S[i] !=S[i+1],f[i][i+1]==1

扰乱字符串(Scramble String)

题目描述

给定一个字符串 s1,我们可以把它递归地分割成两个非空子字符串,从而将其表示为二叉树。

下图是字符串 s1 = “great” 的一种可能的表示形式。

1
2
3
4
5
6
7
    great
/ \
gr eat
/ \ / \
g r e at
/ \
a t

在扰乱这个字符串的过程中,我们可以挑选任何一个非叶节点,然后交换它的两个子节点。

例如,如果我们挑选非叶节点 “gr” ,交换它的两个子节点,将会产生扰乱字符串 “rgeat” 。

1
2
3
4
5
6
7
    rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t

我们将 “rgeat” 称作 “great” 的一个扰乱字符串。

同样地,如果我们继续交换节点 “eat” 和 “at” 的子节点,将会产生另一个新的扰乱字符串 “rgtae” 。

1
2
3
4
5
6
7
    rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a

我们将 “rgtae” 称作 “great” 的一个扰乱字符串。

给出两个长度相等的字符串 s1 和 s2,判断 s2 是否是 s1 的扰乱字符串。

示例 1:

1
2
3
4
5
6
7
Example 1
输入: s1 = "great", s2 = "rgeat"
输出: true

Example 2
输入: s1 = "abcde", s2 = "caebd"
输出: false

戳气球

问题描述

n 个气球,编号为0n-1,每个气球上都标有一个数字,这些数字存在数组 nums 中。

现在要求你戳破所有的气球。如果你戳破气球 i ,就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 leftright 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后,气球 left 和气球 right 就变成了相邻的气球。

求所能获得硬币的最大数量。

说明:

  • 你可以假设 nums[-1] = nums[n] = 1,但注意它们不是真实存在的所以并不能被戳破。
  • 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

示例:

1
2
3
4
输入: [3,1,5,8]
输出: 167
解释: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167

分析

转移方程f[i][j] = max$_{i<k<j}${f[i][k] + f[k][j] + a[i] * a[k] * a[j]}

  1. f[i][j]:扎破i+1~j-1号气球最多获得的金币数
  2. f[i][k]:扎破i+1~k-1号气球最多获得的金币数
  3. f[k][j]:扎破k+1~j-1号气球最多获得的金币数
  4. a[i] * a[k] * a[j]:最后扎破k号气球获得的金币数

初始条件f[0][1] = f[1][2] = ... = f[N][N+1] =0,当没有气球要扎破的时候,最多获得0枚金币

计算顺序:按照长度j-i从小到大的顺序去算

时间复杂度:O(N^3^),空间复杂度:O(N^2^)

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
public int maxCoins(int[] AA) {
int n = AA.length;
if (n == 0)
return 0;
int[] A = new int[n + 2];
A[0] = A[n + 1] = 1; // add two unbreakable balloons
int i, j, k, len;
for (i = 0; i < n; i++)
A[i + 1] = AA[i];
n += 2;
int[][] f = new int[n][n];
// init
for (i = 0; i < n - 1; i++)
f[i][i + 1] = 0;
for (len = 3; len <= n; len++) {
for (i = 0; i <= n - len; i++) {
j = i + len - 1;
f[i][j] = Integer.MIN_VALUE;
// [i] i+1 ... k ... j-1 [j]
// balloon k is the last balloon to burst amang balloon i+1 ... j-1
for (k = i + 1; k < j; k++) {
f[i][j] = Math.max(f[i][j], f[i][k] + f[k][j] + A[i] * A[k] * A[j]);
}
}
}
return f[0][n - 1];
}

能量向量

具体题目链接

描述

在Mars星球上,每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样,通过吸盘(吸盘是Mars人吸收能量的一种器官)的作用,这两颗珠子才能聚合成一颗珠子,同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m,尾标记为r,后一颗能量珠的头标记为r,尾标记为n,则聚合后释放的能量为(Mars单位),新产生的珠子的头标记为m,尾标记为n。

需要时,Mars人就用吸盘夹住相邻的两颗珠子,通过聚合得到能量,直到项链上只剩下一颗珠子为止。显然,不同的聚合顺序得到的总能量是不同的,请你设计一个聚合顺序,使一串项链释放出的总能量最大。

例如:设N=4,4颗珠子的头标记与尾标记依次为(2,3) (3,5) (5,10) (10,2)。我们用记号⊕表示两颗珠子的聚合操作,(j⊕k)表示第j,k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为:
(4⊕1)=1023=60。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为
((4⊕1)⊕2)⊕3)=1023+1035+10510=710。

样例

1
2
3
4
5
Input
4
2 3 5 10
Output
710
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
using namespace std;
int n, head[201], tail[201], f[201][201];
//f[i][j]为起始为i终点为j的链融合生成的最大能量
//head和tail要拓展数组不然越界要考虑模
//珠子 1 2 3 4 5(1) 6(2) 7(3)
//head 1 3 5 7 1 3 5
//tail 3 5 7 1 3 5 7
//没有再考虑4是因为不需要,枚举不到

void read()
{
int i, j, k, len, max1;

cin >> n;
cin >> head[1];
for (i = 2; i <= n; i++)
{
cin >> head[i];

tail[i - 1] = head[i];
}
tail[n] = head[1]; //读入

for (i = n + 1; i <= 2 * n - 1; i++)
{
head[i] = head[i - n];
tail[i] = tail[i - n];
} //拓展数组

for (len = 1; len <= n; len++) //枚举链长
for (i = 1; i <= 2 * n - 1 - len; i++) //枚举起始位置
{
j = i + len; //结束位置

for (k = i; k < j; k++) //寻找在中间某一位置断开,把两边合并
f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + head[i] * tail[k] * tail[j]);
//从i到j的最大能量=max(
// 当前能量,
// 从i到k的最大能量+从k+1到j的最大能量+两颗珠子合并释放的能量
// )
//注意我们把i到k,k+1到j看做两颗已经合并的珠子,只需把这两颗合并
}

max1 = 0;
for (i = 1; i <= n; i++)
if (f[i][n + i - 1] > max1)
max1 = f[i][n + i - 1]; //枚举起始点找最大

cout << max1 << endl;

return;
}

int main()
{
read();
return 0;
}

2020年7月9日更