《算法竞赛——从入门到进阶》读书笔记（7）

e_thinker · 2020-05-10 10:15:41 · 个人记录

第7章动态规划

动态规划（Dynamic Programming，DP）题是算法竞赛中的必出题型。DP是一种常用的算法思想。DP问题可难可易，非常灵活，重点在于对“状态”和“转移”的建模与分析。该算法时间效率高，代码量少。

基础DP

硬币问题

有n种硬币，面值分别为v_1，v_2，v_3，......，v_n。数量无限。输入非负整数s,选用硬币，使其和为s。要求输出最少的硬币组合。

贪心策略：每次选择最大面值。但是这样不一定能得到最优解，甚至在有解的情况下无法算出答案。

不能得到最优解的情形。例如面值是：1,2,4,5,6，支付9元。如果用贪心法，答案是6+2+1。需要3个硬币。而最优的5+4只需要两个硬币。
算不出答案的情形。如果有面值1的硬币，能保证用贪心法得到一个解，如果没有1元硬币，往往得不到解。例如：2,3,5元的硬币，支付9元，用贪心法无法得到解，但解释存在的，即9= 5+2+2。

以上分析，用贪心法解决最少硬币问题要求硬币面值是特殊的。对于任意面值的硬币问题，需要用动态规划来解决。硬币问题是简单的递推问题。

下面以5种面值（1,5,10,25,30）的硬币为例讲解递推的过程。

（1）只使用最小面值的1分硬币。初始值Min[0]=0，其他的Min[i]为无穷大。下面计算Min[1]。同理，i=2时，相当于在Min[1]的基础上加一个硬币，得到Min[2] = Min[2-1]+ 1 =2。继续这个过程。分析上述过程，得到递推关系 Min[i] = min(Min[i],Min[i-1]+1)

（2）在使用1元硬币的基础上增加使用第二大面值的5分硬币，此时，应该从Min[5]开始，因为比5分硬币小的金额不可能用5分硬币实现。i=5时，相当于在i=0的基础上加一个5分硬币，得到Min[5] = Min[5-5] +1=1。上一步用1分硬币的方法有Min[5]=5.取最小值，得Min[5]=1。同理，i=6时，有Min[6]=Min[6-5]+1=2，对比原来的Min[6]=6，取最小值。继续这个过程。分析上述过程，得到递推关系 Min[i] = min(Min[i],Min[i-5]+1)

（3）继续处理其他面值的硬币。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int M=251;    //支付最大金额 
const int V=5;  //5种硬币
int type[V]={1,5,10,25,50};
int Min[M];     // 每种金额对应的最优组合 
void solve() {
    for(int k=0; k<M;k++)   Min[k] =INT_MAX;
    Min[0]=0;
    for(int j=0;j<V;j++) {
        for(int i=type[j];i<M;i++) {
            Min[i]=min(Min[i],Min[i-type[j]]+1);    //递推式 
        }
    }
} 
int main() {
    int s;
    solve();
    while(cin>>s) {
        cout<<Min[s]<<endl;
    }
    return 0;
}

打印最少硬币的组合在最少硬币问题中，如果要求打印组合方案，需要增加一个记录表 $Min\_path[i]$，记录金额$i$需要的最后一个硬币。利用$Min\_path[]$逐步倒推，就能得到所有的硬币。例如，金额$i=6$，$Min \_ path[6] =5$，表示最后一个硬币是5分；然后，$Min\_path[6-5]=1$，查$Min\_path[1]=1$，表示接下来的最后一个硬币是1分；继续$Min\_path[1-1]=0$，不需要硬币了，结束。输出结果为：5+1 ![输出组合](https://cdn.luogu.com.cn/upload/image_hosting/e8g69id6.png) ##### 代码参考 ```cpp #include<bits/stdc++.h> using namespace std; const int M=251; //支付最大金额 const int V=5; //5种硬币 int type[V]={1,5,10,25,50}; int Min[M]; // 每种金额对应的最优组合 int Min_path[M]; //记录最小硬币的路径 void solve() { for(int k=0; k<M;k++) Min[k] =INT_MAX; Min[0]=0; for(int j=0;j<V;j++) { for(int i=type[j];i<M;i++) { if(Min[i] > Min[i-type[j]]+1) { Min_path[i] = type[j]; //在每个金额上记录路径，即某个硬币的面值 Min[i] = Min[i-type[j]]+1; //递推式 } } } } void print_ans(int *Min_path , int s) { //打印硬币组合 while(s) { cout<<Min_path[s]<<" "; s = s-Min_path[s]; } } int main() { int s; solve(); while(cin>>s) { cout<<Min[s]<<endl; //输出最少硬币个数 print_ans(Min_path,s); } return 0; } ``` ##### 所有硬币组合例题： [HDU 2069 coin change](http://acm.hdu.edu.cn/showproblem.php?pid=2069) 题意：有5种面值的硬币，即1分、5分、10分、25分、50分。输入一个钱数s，输入组合方案的数量。例如11分有4种组合方案，即11个1分，2个5分+1个1分、1个5分+6个1分、1个10分+1个1分。$s≤250$，硬币数量$num≤100$。 ------------ 一维不完全解决方案定义一个记录状态的数组 $int$ $ dp[251] $。 $dp[i]$表示金额$i$所对应的组合方案数，即解空间。找到$dp[i]$和 $dp[i-1]$的递推关系，就高效地解决了问题。 ![转移方程表](https://cdn.luogu.com.cn/upload/image_hosting/yq0bmlv2.png) 从“只用1分硬币时”可知，$dp[0]=1$为初始值。$dp[1]$可以从$dp[0]$推导出来：当金额$S=1$时，如果用一个1分硬币，等价于从$s$中减去1分钱，并且硬币数量也减少了一个的情况。此时退到$i=0$；如果$i=0$存在组合方案，那么$i=1$的组合方案也存在。$dp[1] = dp[1]+dp[0]$。对于其他$dp[i]$，同样有$dp[i] = dp[i] + dp[i-1]$ 。 - 在上述分析中，$dp[i]$是“状态”,$dp[i] = dp[i] + dp[i-1]$是状态转移方程。 - 同理可知，“加上5分硬币时”，状态转移方程为：$dp[i]+dp[i]+dp[i-5] $。 - “加上10分硬币时”，状态转移方程为：$dp[i]+dp[i]+dp[i-10] $。 - “加上25分硬币时”，状态转移方程为：$dp[i]+dp[i]+dp[i-25] $。 - “加上50分硬币时”，状态转移方程为：$dp[i]+dp[i]+dp[i-50] $。 ###### 从以上转移方程中可以总结出：状态转移方程为：$dp[i]+dp[i]+dp[i-type[j]] $。 ##### 代码参考 ```cpp #include<bits/stdc++.h> using namespace std; const int M=251; int type[5] ={1,5,10,25,50}; int dp[M] ={0}; void solve() { //预处理 dp[0]=1; for(int i=0;i<5;i++) { for(int j=type[i]; j<M;j++) { dp[j] = dp[j] + dp[j-type[i]]; } } } int main() { int s; solve(); while(cin>>s) { cout<<dp[s]<<endl; } return 0; } ``` 但是上述程序没有考虑对硬币数量的限制。但是原题要求硬币不能多于100个。这是因为状态$dp[i]$太简单，没有记录计算过程中的细节。重新定义状态为$dp[i][j]$，建立一个“转移矩阵”。 ![转移矩阵](https://cdn.luogu.com.cn/upload/image_hosting/7vy6ju0z.png) 矩阵元素$dp[i[[j]$的含义使用$j$个硬币实现金额$i$的方案数。 - 只用1分硬币实现：初始化：$dp[0][0]=1$，其他为0。定义int type[5]={1,5,10,25,50}为5种硬币的面值。从$dp[0][0]$开始，可以推导后面的状态。例如，$dp[1][1]$是$dp[0][0]$进行“金额+1，硬币数量+1”后的状态转移。转移后组合方案数量不变，即$dp[1][1]=dp[0][0]=1$。这里还要考虑$dp[1][1]$原有的方案数，递推关系修正为：$dp[1][1] = dp[1][1]+dp[0][0] = dp[1][1] + dp[1-1][1-1] = 0+1 = 1$。 $dp[1-1][1-1]$的意思是从1分金额中减去1分硬币的钱，原来1个硬币的数量也减少1个。在程序中，把上述操作写成：$dp[1][1] = d[1][1] + dp[1-type[0]][1-1] $。 - 只用5分硬币实现： $dp[i][j] = d[i][j] + dp[i-5][j-1] = dp[i][j] + dp[i-type[1]][j-1] $。 - 只用10分硬币实现： $dp[i][j] = d[i][j] + dp[i-10][j-1] = dp[i][j] + dp[i-type[2]][j-1] $。 - 只用25分硬币实现： $dp[i][j] = d[i][j] + dp[i-25][j-1] = dp[i][j] + dp[i-type[3]][j-1] $。 - 只用50分硬币实现： $dp[i][j] = d[i][j] + dp[i-50][j-1] = dp[i][j] + dp[i-type[4]][j-1] $。 ###### 从以上转移方程式中可以总结出：$dp[i][j] = d[i][j] + dp[i-type[k]][j-1] ， k=2,3,4 $。 ##### 代码实现 ```cpp #include<bits/stdc++.h> using namespace std; const int M=251; int type[5] ={1,5,10,25,50}; int dp[M] ={0}; void solve() { //预处理 dp[0]=1; for(int i=0;i<5;i++) { for(int j=type[i]; j<M;j++) { dp[j] = dp[j] + dp[j-type[i]]; } } } int main() { int s; solve(); while(cin>>s) { cout<<dp[s]<<endl; } return 0; } ``` ### 0/1背包问题 0/1背包问题是最经典的DP问题，没有之一。问题：给定$n$种物品和一个背包，物品$i$的重量是$w_i$、价值为$v_i$，背包的总容量为$C$。在装入背包的物品时对每种物品$i$只有两种选择，即装入背包和不装入背包（称为0/1背包）。如何选择装入背包的物品，使得装入背包的物品的总价值最大？例子：有4个物品，其重量分别是2、3、6、5，价值分别为6、3、5、4，背包的容量为9。 ###### 例题 - [01背包问题](https://www.acwing.com/problem/content/2/) - [P1048 采药](https://www.luogu.com.cn/problem/P1048) ------------ #### 用DP求解0/1背包引进一个 $(n+1)×(C+1)$的二维表dp[ ][ ]，可以把每个$dp[i][j]$都看成一个背包，$dp[i][j]$表示把前$i$个物品装入容量为$j$的背包中获得的最大价值，$i$是纵坐标，$j$是横坐标。填表按照只装第1个物品、只装前两个物品、只装前3个物品的顺序，知道装完。如图所示，这是从小问题扩展到大问题的过程。 ![表1](https://cdn.luogu.com.cn/upload/image_hosting/oeteeddb.png) 步骤1：只装第1个物品。由于物品1的重量2，所以背包容量小于2的都放不进去，得$dp[1][0] = dp[1][1] = 0$；物品1的重量等于背包容量，装进去，背包价值等于物品1的价值，$dp[1][2]=6$；容量大于2的背包，多余的容量用不到，所以价值和容量2的背包一样。步骤2：只装前2个物品。如果物品2的重量比背包容量大，那么不能装物品2，情况和只装第1个物品一样。下面填$dp[2][3]$时，物品2的重量等于背包容量，那么可以装物品2，也可以不装。 - （1）如果装物品2（重量是3），那么相当于把只把物品1装到（容量-3）的背包中。 - （2）如果不装物品2，那么相当于只把物品1装到背包中。取（1）（2）的最大值，得$dp[2][3] = max\{3,6\} = 6

后续步骤：继续以上过程，最后得到结果。最后的答案是dp[4][9]，即把4个物品装到容量为9的背包，最大价值是11。

输出0/1背包方案

现在回头看具体装了哪些物品，需要倒过来观察：

用实线箭头指出方案路径

代码参考

#include<bits/stdc++.h>
using namespace std;
const int M=1010;
int f[M][M];    //物品，容量
bool c[M];  //记录物品是否选择 ，默认没有选择 
int n,m;
int v[M],w[M]; 
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)   cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=m;j++) {
            f[i][j] = f[i-1][j];    //不选物品的总价值 
            if(j>=v[i]) {
                f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]) ;    //选物品的总价值 ， 取最大值

            } 
        }
    }
    // 输出方案 
    for(int i=n,j=m;i>0;i--) {
        if(j-v[i]>=0 && f[i-1][j] < f[i-1][j-v[i]]+w[i])  {
            c[i]=1; j-=v[i];
        }
        else    c[i]=0; 

    }
    cout<<f[n][m]<<endl;    //输出选4个物品，限体积4 的最大值 
    for(int i=1;i<=n;i++)   if(c[i])    cout<<i<<" ";
    return 0; 
}

滚动数组

在处理dp[ \ \ ][ \ \ ]状态数组的时候有一个小技巧：把它变成一维的dp[ \ \ ] ，以节省空间。观察上面的二维表dp[ \ \ ][ \ \ ] 可以发现，每一行是从上面一行算出来的，只跟上一行有关系，跟更前面的行没有关系。那么用新的一行覆盖原来的一行就可以了。

代码参考

#include<bits/stdc++.h>
using namespace std;
const int M=1010;
int f[M];   //物品，容量
bool c[M];  //记录物品是否选择 ，默认没有选择 
int n,m;
int v[M],w[M]; 
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)   cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++) {
        for(int j=m;j>=v[i];j--) {  //注意：反过来循环 
            f[j] = max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m]<<endl;   //输出限体积4 的最大值 
    return 0;
}

注意，j应该反过来循环，即从后面往前面覆盖。

经过滚动数组的优化，空间复杂度从O(NV) 减少为O(V)。

动态规划题经常会给出很大的N,V，此时需要使用滚动数组，否则会 MLE。

滚动数组也有缺点，它覆盖了中间转移状态，只留下了最后的状态，所以损失了很多信息，导致无法输出背包的方案。

最长公共子序列

题目：最长公共子序列

最长公共子序列（Longest Common Subsequence ，LCS）问题：给定两个序列X和Y，找出X和Y的一个最长公共子序列。

用暴力法找最长公共子序列需要先找出X的所有子序列，然后验证是否为Y的子序列。如果X有m个元素，那么X有2^m个子序列，若Y有n个元素，总复杂度大于O(n2^m)。用动态规划求LCS，复杂度是O(nm)

例如，序列X = (a,b,c,f,b,c)、 Y = (a,b,f,c,a,b)。

用L[i][j]表示子序列X_i和Y_j的最长公共子序列的长度。

代码参考

#include<bits/stdc++.h>
using namespace std;
const int M=1010;
char a[M],b[M];
int dp[M][M]; 
int n,m;
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)   cin>>a[i];
    for(int i=1;i<=m;i++)   cin>>b[i];
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(a[i] == b[j])    dp[i][j] = dp[i-1][j-1]+1;
            else {
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    cout<<dp[n][m]; 
    return 0;
}

如果要输出方案，和0/1背包的输出方案一样，LCS需要从后面倒推回去。

最长上升子序列

最长上升子序列（Longest Increasing Subsequence, LIS）问题：给定一个长度为N的数组，找出一个最长的单调递增子序列。例如一个长度为7的序列A=\{ 5,6,7,4,2,8,3 \}，它最长的单调递增子序列为\{ 5,6,7,8 \ },长度为4

P1020 导弹拦截

这个题目的思维转换有一些难度。题目的意思是统计一个序列中的单调递减子序列最少有多少个。这和最长递增子序列LIS有什么关系呢？假设已经有了求LIS的算法，可以这么转换：把序列反过来，就变成了了求反序列的递增子序列；先求反序列的第1个LIS，然后从原序列中去掉这个LIS，再对剩下的求第2个LIS，直到序列为空；这些LIS的数量就是题目的解。但是，其实并不用这么麻烦，这个题目实际上等价于求原序列的LIS，这是一道求LIS的裸题。

模拟计算过程：

从第一个数开始，找一个最长的递减子序列。第一拦截系统X：{389, 300, 299, 170, 158, 65}
去掉这些数，序列中还剩下{207, 155}。第二个拦截系统Y： {207,155}。

结论：在Y中，至少有一个数a大于X中的某个数，否则a比X的所有数都小，应该在X中。所以，从每个拦截系统中拿出一个数能构成一个递增子序列，即拦截系统的数量等于这个递增子序列的长度。

方法1：上一节讲解了最长公共子序列LCS，可以借助LCS思想，首先对序列排列，得到A’= {65, 158, 170, 299, 300, 389}，那么A的LIS就是A和A'的LCS。其复杂度是O(n^2)。

方法2：直接用DP求解LIS。复杂度也是O(n^2)。

定义状态dp[i]，表示以第i个数为结尾的最长递增子序列的长度，那么：dp[i] = max \{ 0,dp[j] \}+1, 0<j<i , A_j < A_i。最后答案是max\{ dp[i] \}

代码参考

#include<bits/stdc++.h>
using namespace std;
const int M=100010;
int n,h[M];
//最长递增子序列
int LIS() {
    int ans=1;  //至少一个拦截系统
    int dp[M];
    dp[1]=1;
    for(int i=2;i<=n;i++) {
        int max=0;
        for(int j=1;j<i;j++) {
            if(dp[j]>max && h[i]>h[j])  max=dp[j];          
        }
        dp[i]=max+1;    //更新dp 
        if(dp[i]>ans)   ans=dp[i];  //取最大值 
    } 
    return ans;
} 

//最长递减子序列
int LDS() {
    int ans=1;  //至少一个拦截系统
    int dp[M];
    dp[1]=1;
    for(int i=2;i<=n;i++) {
        int max=0;
        for(int j=1;j<i;j++) {
            if(dp[j]>max && h[i]<h[j])  max=dp[j];      //主要修改该条件   
        }
        dp[i]=max+1;    //更新dp 
        if(dp[i]>ans)   ans=dp[i];  //取最大值 
    } 
    return ans;
} 

int main() {
    cin>>n;
    for(int i=1;i<=n;i++)   cin>>h[i];
    cout<<LDS()<<endl;
    cout<<LIS();
    return 0;
}

方法3：有一种更快的、复杂度为O(n log_2 n)的方法。这个方法不是DP算法，它巧妙地利用了序列本身的特征，通过一个辅助数组d[ ]统计最长递增子序列的长度。

定义：数组d[ ]； len统计d[ ] 内数据的个数； high[ ] 为原始序列。

初始化： d[1] = high[1]， len=1；

操作步骤：逐个处理high[ ] 中的数字，例如处理到了high[k]，①如果high[k]比d[]末尾的数字更大，就加到d[]的后面； ②如果high[k]比d[]末尾的数字小，就替换d[]中第1个大于它的数字。

以high ={4,8,9,5,6,7}为例。具体操作过程如下：

代码参考

#include<bits/stdc++.h>
using namespace std;
const int M=100010;
int n,h[M];
//最长递增子序列
int LIS() {
    int len=1;
    int d[M];
    d[1]=h[1];
    for(int i=2;i<=n;i++) {
        if(h[i]> d[len])    d[++len] = h[i];
        else {
            int j=lower_bound(d+1,d+1+len,h[i]) -d;
            d[j]=h[i];
        }
    }
    return len;
} 
int main() {
    cin>>n;
    for(int i=1;i<=n;i++)   cin>>h[i];
    cout<<LIS();
    return 0;
}

区间DP

区间DP的主要思想是先在小区间进行DP得到最优解，然后再利用小区间的最优解合并求大区间的最优解。

区间DP，一般需要从小到大枚举所有可能的区间。在解题时，先解决小区间问题，然后合并小区间，得到更大的区间，直到解决最后的大区间问题。合并的操作一般是把左、右两个相邻的子区间合并。

区间DP的两个难点：枚举所有可能的区间、状态转移方程。

区间DP的复杂度：一个长度为n 的区间，它的子区间数量级为O(n^2)，每个子区间内部处理时间不确定，合起来复杂度会大于O(n^2)。在编程时，区间DP至少需要两层for循环，第1层的i从区间的首部或尾部开始，第2层的j从i开始到结束，i和j一起枚举出所有的子区间。

石子合并问题

题目链接：石子并问题

样例：3堆石子： 2，4，5，最小花费17。

计算过程：① 第一次合并2+4=6 ； ②第二次合并：6+5=11 ；总花费是6+11=17。

DP的状态设计

设dp[i][j]为从第i堆石子到第j堆石子的最小花费，那么dp[1][n]就是答案。另外，设sum[i][j]为从第i到j的区间和。

（1）合并之前，dp[i][i]=0， 1≤i≤n

（2）两堆合并，例如：dp[1][2] = dp[1][1]+ dp[2][2]+sum[1][2]；总结：dp[i][i+1] = dp[i][i]+dp[i+1][i+1]+sum[i][i+1]
（3）三堆合并：合并第1堆到第3堆，有两种情况。dp[1][3]= min(dp[1][1]+dp[2][3], dp[1][2]+dp[3][3])+sum[1][3]；总结： dp[i][i+2] = min(dp[i][i]+dp[i+1][i+2],dp[i][i+1]+dp[i+2][i+2])；
（4）推广：第i堆到第j堆的合并。dp[i][j]=min(dp[i][k]+dp[k+1][j])+sum[i][j-i+1], i≤k≤j。这就是状态转移方程式。

代码参考

#include<bits/stdc++.h>
using namespace std;
const int M=310;
const int INF=1<<30;
int a[M];   //石子颗数
int n;  //堆数
int dp[M][M];   //花费 
int sum[M];     //前n项和 
int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];  
        sum[i]= sum[i-1]+a[i];  //计算前n项和 
    }
    for(int len=1;len<n;len++) {    //len为i 和 j 的距离 
        for(int i=1;i<=n-len;i++) { // 表示从第i堆开始 
            int j=i+len;    //表示到第j堆结束
            dp[i][j] = INF; //求最小值，默认值为无穷大 
            for(int k=i ; k<j; k++) {   //i和j之间用k进行分割 
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);  //sum[i][j] = sum[j] - sum[i-1]  
            } 
        } 
    } 
    cout<<dp[1][n];
    return 0;
}

复杂度是O(n^3)。那么是否可以优化？在它的三重循环中，前两重循环是枚举所有可能的合并，无法优化，最后一层循环枚举分割点k，是可以优化的。因为每次运行最后一层循环时都在某个子区间内部寻找最优分割点，该操作在多个子区间里是重复的。如果找到这个最优点后保存下来，用于下一次循环，就能避免重复计算，从而降低复杂度。

用s[i][j]表示区间[i,j]中的最优分割点，第三重循环可以从区间[i,j-1)的枚举优化到区间[s[i][j-1] , s[i+1][j]]的枚举。其中s[ \ ][ \ ]值是在前面的三重循环中找到并记录下来的。

上述讨论符合“四边形不等式”优化原理，它是区间DP的常见优化方法。经过优化以后，复杂度接近O(n^2)，可以解决n<3000的问题。

代码参考

// 四边形不等式优化
#include<bits/stdc++.h>
using namespace std;
const int M=310;
const int INF=1<<30;
int a[M];   //石子颗数
int n;  //堆数
int dp[M][M];   //花费 
int sum[M];     //前n项和 
int s[M][M]; 
int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];  
        sum[i]= sum[i-1]+a[i];  //计算前n项和
        s[i][i] = i;    //初始最佳分割点 
    }
    for(int len=1;len<n;len++) {    //len为i 和 j 的距离 
        for(int i=1;i<=n-len;i++) { // 表示从第i堆开始 
            int j=i+len;    //表示到第j堆结束
            dp[i][j] = INF; //求最小值，默认值为无穷大 
            for(int k=s[i][j-1]  ; k<= s[i+1][j]; k++) {    //i和j之间用k进行分割, 缩小范围 
                if(dp[i][k] + dp[k+1][j] + sum[j]- sum[i-1] < dp[i][j]) {
                    dp[i][j] = dp[i][k] + dp[k+1][j] + sum[j]- sum[i-1];
                    s[i][j] = k;    //记录[i,j]的最优分割点 
                }
            } 
        } 
    } 
    cout<<dp[1][n];
    return 0;
}

回文串

题目：P2890 回文串

题意：给定字符串s，长度为m，由n个小写字母构成。在s的任意位置增删字母，把它变成回文串，增删特定字母的花费不同。求最小花费。

样例解释：在结尾处插入"a"，得到"abcba"，花费1000；如果在首端删除"a"得到"bcb"，花费1100；如果在首端插入"bcb"，花费350+200+350=900,这是最小值。

该题有多种解法，其中一种是把s反转得到s'，求得两者最长公共子序列的长度l，用s的长度减去l就是答案。

下面用区间DP的方法求解。

定义状态dp[i][j]表示字符串s的子区间s[i,j]变成回文的最小花费。

另外，在考虑删除和插入的花费时，由于这两种操作时等价的（这头加和那头减一样），所以只要取这两种操作的最小值就行了。用数组w[ \ ]定义字符的花费。

有以下3种情况：

(1)如果s[i] == s[j]，那么dp[i][j] = dp[i+1][j-1]；
(2)如果dp[i+1][j]是回文串，那么dp[i][j] = dp[i+1][j]+w[i]；
(3)如果dp[i][j-1]是回文串，那么dp[i][j] = dp[i][j-1]+w[j]。

代码参考

#include<bits/stdc++.h>
using namespace std;
const int M=2010;
int w[30],n,m,dp[M][M];
char s[M],ch;

int main() {
    int x,y;
    cin>>n>>m;
    cin>>s;
    for(int i=1;i<=n;i++) {
        cin>>ch>>x>>y;  w[ch - 'a'] = min(x,y); //取最小值 
    }   
    for(int i=m-1;i>=0;i--) {       // i是子区间的起点 
        for(int j=i+1;j<m;j++) {    // j是子区间的终点 
            if(s[i] == s[j])    dp[i][j] = dp[i+1][j-1];
            else {
                dp[i][j] = min(dp[i+1][j]+w[s[i]-'a'] , dp[i][j-1]+w[s[j]-'a']) ;
            }   
        }   
    }
    cout<<dp[0][m-1]<<endl;
    return 0;
}

《算法竞赛——从入门到进阶》读书笔记（7）

第7章动态规划

基础DP

硬币问题

代码实现

代码参考

代码参考

最长公共子序列

代码参考

最长上升子序列

代码参考

代码参考

区间DP

石子合并问题

代码参考

代码参考

回文串

代码参考

树形DP

数位DP

状态压缩DP

《算法竞赛——从入门到进阶》读书笔记（7）

第7章 动态规划

基础DP

硬币问题

代码实现

代码参考

代码参考

最长公共子序列

代码参考

最长上升子序列

代码参考

代码参考

区间DP

石子合并问题

代码参考

代码参考

回文串

代码参考

树形DP

数位DP

状态压缩DP

第7章动态规划