dp进阶之路(二)——线性dp（2）

例2：顺序对齐

题目大意：虑两个字符串右对齐的最佳解法。例如，有一个右对齐方案中字符串是aaddefgghc和adcdegh。
第一行:
第二行:
每一个数值匹配的位置值2分，一段连续的空格值-1分。所以总分是匹配点的2倍减去连续空格的段数，在上述给定的例子中，6个位置(A,D,D,E,G,H)匹配，三段空格，所以得分，注意，我们并不处罚左边的不匹配位置。若匹配的位置是两个不同的字符，则既不得分也不失分。
请你写个程序找出最佳右对齐方案。（字符串长度小于等于50）
思路：
状态设计为：f[i][j]表示两个字符串的后i，j个字符对应的最大值
转移分成三种情况：
1.直接放在对应位置，两个字母不相同
2.放在对应位置，相同
3.有空格
那么转移方程为：
没空格 ： f[i][j] = f[i + 1][j + 1]
如果s1[i] == s2[j - 1] ： f[i][j] = max(f[i + 1][j + 1] + 2, f[i][j])
如果s1前面有连续空格 ：f[i][j] = max(f[k][j] - 1, f[i][j])
如果s2前面有连续空格 ：f[i][j] = max(f[i][k] - 1, f[i][j])
注意， 由于前面的空格不算，所以答案是所有f[i][j]里最大的一个……
假设ij之前都不等，最开头加空格）
思考：
当dp的状态确定了之后，一般问题就简单了——分类讨论就行。

例3：HDU 4055 Number String

题目大意：
由数字1到n组成的所有排列中，问满足题目所给的n-1个字符的排列有多少个，如果第i字符是‘I’表示排列中的第i-1个数是小于第i个数的。如果是‘D’，则反之。
example：“ID” 对应 132， 231 ； “I?” 对应 123 132 231
思路：
题目求什么我们就把什么往状态里面放，显然这里状态里肯定有i——表示串的长度，然后为了后面能一个一个数字加进去，我们显然需要在用一个j来记录当前这个串末尾是什么。
f[i][j] 表示长度为i，末尾为j的序列的个数。】、
于求的是1..n的排列（不能有重复的元素），所以f[i][j]实际上还隐含一个条件————目前这个序列里面每个元素小于等于i， 如果没有这个条件，当前选了那些元素也是影响答案的一个因素（不知道就没法转移）。
但是这样也就等于我每次都只能加i，可是最后一位是j啊？？
我们可以把(1,i-1)中大于等于j的变成j+1，这样既不破坏增减性又不影响结果数目。
所以转移方程如下：
如果s[i - 1]等于I dp[i][j] = summ[i - 1][j - 1];
如果s[i - 1]等于D dp[i][j] = summ[i - 1][i] - summ[i - 1][j - 1];}
如果s[i - 1]等于? dp[i][j] = summ[i - 1][i];}
summ[i][j]表示长度为i，末尾小于等于j的所有序列之和。(边求解即可边维护前缀和)
思考：
dp的相同子问题和最优子结构不仅是判断动规的条件，也是要在动规的方程中体现出来的，将问题范围缩小的过程中（即寻找相同子问题的过程中），什么量是要一块缩小的，哪些量又是可以不缩小的，是值得思考的问题（思考完这个，状态也该出来了）！
本题还有一个注意点是：通过前缀和的维护将转移的复杂度降了一维，这提醒我们————即使是转移过程中会改变的量，如果满足前缀和的性质也是可以一边转移一边求和然后用的哦！