笔记

最优子结构：子结构最优，全局一定最优 无后效性：各个决策部分单独存在，不会相互影响

1. 确定状态
   • 维度从低往高试
2. 确定转移方程
   • 每一个状态的决策
   • 初始值
   • 边界问题
3. 是否可以降低维度或其他优化

最大子串和

题意：给你一个有正有负的序列，求一个=子串（连续的一段），使其和最大！ 样例输入： -5 6 -1 5 4 -7 样例输出： 14

状态：f[i]表示前i个数的最大子串和，每个状态只有两种决策：1. 与前面构成一个子串 2. 单独成为一个子串的开头 转移方程: f[i]=max(f[i−1]+a[i],a[i])f[i]=max(f[i−1]+a[i],a[i])

不相交的两个子串的最大和

给你一个有正有负的序列，求两个不重叠的子串，使其和最大！

方法一

两个不重叠的子串中间一定有一个分界点，我们可以枚举这个分界点，分别求出这个点左边的最大子串和以及右边的最大子串和

方法二

定义状态f[i][j]为前i个数组成了j个子串的最大值，当前状态下有两种选择，一种是与前面组成子串，一种是单独成为一个子串，但是需要枚举这个数前面的串的结尾在哪里 状态转移方程为f[i][j]=max(f[i−1][j]+a[i],f[k][j−1]+a[i],0<k<if[i][j]=max(f[i−1][j]+a[i],f[k][j−1]+a[i],0<k<i​ 优化：可以用前缀和维护k维度，算出前k个数的最大和

最大子矩形

在一个矩阵中找到一个子矩阵，该子矩阵和最大！！输出最大和即可。

从暴力的角度考虑，这道题需要枚举矩形的两个顶点，也就是O(n^4) 我们可以只枚举两个顶点的行坐标，即找到这个矩形的高度所在的位置，然后把每一列的数之和求出来当做一个数，可以提前求出每一列前缀和，也就转化成了求最大子串和。

最长公共子序列

给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 最长公共子序列:公共子序列中长度最长的子序列。 给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…, yn}，找出X和Y的一个最长公共子序列。

状态：f[i][j]表示X的前i位与Y的前j位最长公共子序列的长度 转移方程：

for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
    if(X[i]==Y[j]) f[i][j]=f[i-1][j-1]+1;
    else f[i][j]=max(f[i-1][j],f[i][j-1]);
}

回文词

回文词是一种对称的字符串——也就是说，一个回文词，从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。你的任务是写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。比如字符串“Ab3bd”，在插入两个字符后可以变成一个回文词（“dAb3bAd”或“Adb3bdA”）。然而，插入两个以下的字符无法使它变成一个回文词。 给出一个字符串求出使其变为回文串需要插入的最少字符数。

思路：需要添加的字符的长度为原字符串的总长度减去现有的回文串长度，所以只要求出原字符串的回文串的长度就可以解决了 回文串的定义是正串与反串一样，那么正串与反串的最长公共子序列长度就是回文串的长度 *为什么不是最长公共子串长度？* 在添加字符的时候可以在任意位置插入，所以不必要求连续。所以如果只能从左右两边加入，那么就是最长公共子串长度

乘积最大

设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。 如：有一个数字串：312， 当N=3，K=1时会有以下两种分法：1） 312=362） 312=62 这时，符合题目要求的结果是：31*2=62

状态：f[i][j]表示前i位使用k个乘号的最大乘积 决策：

1. 这个数与前面的数组成更大的数，需要枚举这个数的起点
2. 单独成为一个新数

*在算乘积的时候可以先算出前缀‘乘’* 转移方程:

for(int i=1;i<=n;i++)
    muti[i]*=muti[i-1]*a[i];
muti[0]=1;

for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
{
    f[i][j]=f[i-1][j-1]*a[i];
    for(int k=1;k<i;k++)
        f[i][j]=f[k][j-1]*(muti[i]/muti[k-1]);
}