【算法篇】动态规划（二）

分割回文字符串

class Solution {
public:bool isPal(string& s,int begin,int end){while(begin<end){if(s[begin]!=s[end]){return false;}begin++;end--;}return true;}int minCut(string s) {int len=s.size();vector<int> segsize(len+1);if(len==0)//空串{return 0;}if(isPal(s,0,len-1))//整体都为回文{return 0;}//进行初始化，每个字符位置的最大分割次数for(int i=1;i<=len;i++){segsize[i]=i-1;}for(int i=2;i<=len;i++){//判断0~i之间是否都为回文，因为要取的是最小值if(isPal(s,0,i-1)){segsize[i]=0;}//下面从j=1开始是因为上面已经将0~i-1已经判断过了for(int j=1;j<i;j++){//j<i&&isPal(s,j,i-1),min(segsize[i],segsize[j]+1)//取最小值，可能为零也可能是距离上一个回文的值加1if(j<i&&isPal(s,j,i-1)){segsize[i]=min(segsize[i],segsize[j]+1);}}}return segsize[len];}
};

class Solution {
public:vector<vector<bool>> GetMat(string & s){int n=s.size();vector<vector<bool>> Mat(n,vector<bool>(n,false));//这里为什么是从大到小遍历，看下面的图片//s[i]==s[j]&&f(i+1;j-1)是回文因为要找i+1;j-1它们之间的区间，也就需要向下查找for(int i=n-1;i>=0;i--){//这里i是小于等于j的for(int j=i;j<n;j++){if(i==j){Mat[i][j]=true;}else if(i+1==j){Mat[i][j]=s[i]==s[j];}else{Mat[i][j]=(s[i]==s[j])&&(Mat[i+1][j-1]);}}}return Mat;}int minCut(string s) {int len=s.size();vector<int> segsize(len+1);vector<vector<bool>> Mat=GetMat(s);if(len==0)//空串{return 0;}if(isPal(s,0,len-1))//整体都为回文{return 0;}//进行初始化，每个字符位置的最大分割次数for(int i=0;i<=len;i++){segsize[i]=i-1;}for(int i=2;i<=len;i++){//判断0~i之间是否都为回文，因为要取的是最小值//下面从j=1开始是因为上面已经将0~i-1已经判断过了for(int j=0;j<i;j++){//j<i&&isPal(s,j,i-1),min(segsize[i],segsize[j]+1)//取最小值，可能为零也可能是距离上一个回文的值加1if(Mat[j][i-1]){segsize[i]=min(segsize[i],segsize[j]+1);}}}return segsize[len];}
};

编辑距离

class Solution {
public:int minDistance(string word1, string word2) {int row=word1.size();int col=word2.size();vector<vector<int>> mindis(row+1,vector<int>(col+1));for(int i=0;i<row+1;i++){mindis[i][0]=i;}//[0][0]位置已经初始化过了for(int j=1;j<col+1;j++){mindis[0][j]=j;}for(int i=1;i<=row;i++){for(int j=1;j<=col;j++){//选择插入或者删除mindis[i][j]=min(mindis[i-1][j],mindis[i][j-1])+1;//替换if(word1[i-1]==word2[j-1])//字符的位置与数组的位置相差一{//如果相等的话，就直接取mindis[i-1][j-1]，但是也是需要比较一下的mindis[i][j]=min(mindis[i][j],mindis[i-1][j-1]);}else{//替换和插入删除进行比较，mindis[i-1][j-1]+1因为不相等所以要加一mindis[i][j]=min(mindis[i][j],mindis[i-1][j-1]+1);}}}return mindis[row][col];}
};

不同的子序列

class Solution {
public:int numDistinct(string s, string t) {// if (s.length() < t.length()) return 0;// int row=s.size();// int col=t.size();// //vector<vector<int>> dp(row+1,vector<int>(col+1));// vector<vector<unsigned int>> dp(row+ 1, vector<unsigned int>(col + 1, 0));// dp[0][0]=1;// for(int i=1;i<=row;i++)// {//     dp[i][0]=1;//     for(int j=1;j<=col;j++)//     {//         if(s[i-1]==t[j-1])//         {//             dp[i][j]=dp[i-1][j-1]+dp[i-1][j];//         }//         else//         {//             dp[i][j]=dp[i-1][j];//         }//     }// }// return dp[row][col];//下面的方法解释了空间，思想还是一样的if (s.length() < t.length()) return 0;int row=s.size();int col=t.size();//vector<vector<int>> dp(row+1,vector<int>(col+1));vector<unsigned int> dp(row+ 1);dp[0]=1;for(int i=1;i<=row;i++){//为什么要从大到小进行，dp[j-1]+dp[j];是要取上一行的//所以就导致到从后开始，如果从前开始就会导致并不是从上一行当中取值//而是在该行当中取值for(int j=col;j>0;j--){if(s[i-1]==t[j-1]){dp[j]=dp[j-1]+dp[j];}else{dp[j]=dp[j];}}}return dp[col];}
};

数组当中类型的问题，int,long long,unsigned int

1、long long比unsigned int表示范围大 2、之所以unsigned int没问题，大概是因为编译器优化了（以下为我根据实测情况下的猜测，测试方法为，给unsigned int对象初始化一个超过上限的值，能正确打印出翻转后的值，但如果这个值非常大，则会报错）：unsigned int能接受的实际值超过它的上限，当实际值超过unsigned int上限，会自动翻转（可以理解为取模）变成一个很小的数。 3、long long则不然，因为不能翻转，累加会越来越大，直到爆炸。

动态规划解题思路

动规状态定义：
状态来源：从问题中抽象状态
抽象状态：每一个状态对应一个子问题
状态的形式可以定义很多，如何验证状态的合理性：

1、某一状态的解或者多个状态处理之后解能否对应最终问题的解
2、状态之间可以形成递推关系

一维状态VS二维状态（依据问题和题目线索）：

首先尝试一维状态
一维状态的合理性不满足时，再去定义二维状态

常见问题的状态：

字符串：状态一般对应字串，状态中每次一般增加一个新的字符
矩阵：二维状态–》优化—》一维状态（有机会变为一维，并不是肯定）