九章算法笔记D6-区间型动态规划
@[toc]
D6 区间型动态规划
类型
- 给定一个序列/字符串,进行一些操作
- 最后一步会将序列/字符串去头/去尾
- 剩下的会是一个区间
[i,j]
- 状态自然定义为
f[i][j]
,表示面对子序列[i,...,j]
时的最优性质 - 千万不能按照i的顺序去算!按照长度从小到大去算
1 | for(int l=2;l<=n;l++) |
最长回文子序列
描述
给一字符串 s, 找出在 s 中的最长回文子序列的长度. 你可以假设 s 的最大长度为 1000
.
样例1
1 | 输入: "bbbab" |
分析
转移方程: 设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 | great |
在扰乱这个字符串的过程中,我们可以挑选任何一个非叶节点,然后交换它的两个子节点。
例如,如果我们挑选非叶节点 “gr” ,交换它的两个子节点,将会产生扰乱字符串 “rgeat” 。
1 | rgeat |
我们将 “rgeat” 称作 “great” 的一个扰乱字符串。
同样地,如果我们继续交换节点 “eat” 和 “at” 的子节点,将会产生另一个新的扰乱字符串 “rgtae” 。
1 | rgtae |
我们将 “rgtae” 称作 “great” 的一个扰乱字符串。
给出两个长度相等的字符串 s1 和 s2,判断 s2 是否是 s1 的扰乱字符串。
示例 1:
1 | Example 1 |
戳气球
问题描述
有 n
个气球,编号为0
到 n-1
,每个气球上都标有一个数字,这些数字存在数组 nums
中。
现在要求你戳破所有的气球。如果你戳破气球 i
,就可以获得 nums[left] * nums[i] * nums[right]
个硬币。 这里的 left
和 right
代表和 i
相邻的两个气球的序号。注意当你戳破了气球 i
后,气球 left
和气球 right
就变成了相邻的气球。
求所能获得硬币的最大数量。
说明:
- 你可以假设
nums[-1] = nums[n] = 1
,但注意它们不是真实存在的所以并不能被戳破。 - 0 ≤
n
≤ 500, 0 ≤nums[i]
≤ 100
示例:
1 | 输入: [3,1,5,8] |
分析
转移方程:f[i][j]
= max$_{i<k<j}${f[i][k]
+ f[k][j]
+ a[i] * a[k] * a[j]}
f[i][j]
:扎破i+1~j-1
号气球最多获得的金币数f[i][k]
:扎破i+1~k-1
号气球最多获得的金币数f[k][j]
:扎破k+1~j-1
号气球最多获得的金币数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 | public int maxCoins(int[] AA) { |
能量向量
描述
在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 | Input |
1 |
|