网站文章页301重定向怎么做,qq云端服务器,多功能垫块机,淘宝客优惠券网站建设加盟官网链接#xff1a;
1312. 让字符串成为回文串的最少插入次数
题意#xff1a;
如题
解#xff1a;
动态规划#xff0c;枚举回文串中点并递增回文串长度
初始状态若LR则单个字符为中点#xff0c;需要添加0个字符成为回文串#xff1b;若L1R则如果S[L]S[R]则需要添加…链接
1312. 让字符串成为回文串的最少插入次数
题意
如题
解
动态规划枚举回文串中点并递增回文串长度
初始状态若LR则单个字符为中点需要添加0个字符成为回文串若L1R则如果S[L]S[R]则需要添加0个字符成为回文串否则添加1个字符选其一但是并不需要知道加的是那个
状态转移
如果S[L]!S[R]则DP[L][R] min(dp[i 1][j] 1, dp[i][j - 1] 1, dp[i 1][j - 1]1)但是dp[i 1][j - 1]1其实至少等价于其中之一比如abc需要添加a和c变成acbca或cabac那么ab和bc都为1,abc2(ab1)1(bc1)1或者aac需要添加cac需要添加1aa需要添加0则aac1(aa)1(ac1)1
如果s[L]S[R]则DP[L][R]min(DP[L][R],DP[L1][R-1])
实际代码
#includebits/stdc.h
using namespace std;
int minInsertions(string s)
{int lgs.size();vectorvectorint dp(lg,vectorint(lg,0x3f3f3f3f));for(int i0;ilg;i) dp[i][i]0;for(int t1;tlg;t)//递增推导长度 {for(int i0;itlg;i)//递增起点 {if(t1){if(s[i]s[it]) dp[i][it]0;else dp[i][it]1;}else{dp[i][it]min(dp[i][it-1]1,dp[i1][it]1);if(s[i]s[it]) dp[i][it]min(dp[i][it],dp[i1][it-1]);}}}return dp[0][lg-1];
}
int main()
{string s;cins;int ansminInsertions(s);coutansendl;return 0;
}限制
1 s.length 500s 中所有字符都是小写字母。
