個人主頁：兜里有顆棉花糖
歡迎 點贊?? 收藏? 留言? 加關注??本文由 兜里有顆棉花糖 原創(chuàng)
收錄于專欄【手撕算法系列專欄】【LeetCode】
??本專欄旨在提高自己算法能力的同時，記錄一下自己的學習過程，希望對大家有所幫助
??希望我們一起努力、成長，共同進步。
點擊直接跳轉到該題目
1??題目描述
給你一個字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
請你返回讓 s 成為回文串的 最少操作次數(shù) 。
「回文串」是正讀和反讀都相同的字符串。
示例1：
輸入：s = “zzazz”
輸出：0
解釋：字符串 “zzazz” 已經(jīng)是回文串了，所以不需要做任何插入操作。
示例2：
輸入：s = “mbadm”
輸出：2
解釋：字符串可變?yōu)?“mbdadbm” 或者 “mdbabdm” 。
示例3：
輸入：s = “l(fā)eetcode”
輸出：5
解釋：插入 5 個字符后字符串變?yōu)?“l(fā)eetcodocteel” 。
注意：
1 <= s.length <= 500s 中所有字符都是小寫字母。
2??題目解析
狀態(tài)表示：
-
dp[i][j]：表示區(qū)間[i,j]字符串稱為回文串的最少插入次數(shù)。
狀態(tài)轉移方程如下圖：
返回值：文章來源：http://www.zghlxwxcb.cn/news/detail-741885.html
dp[0][n-1]
3??解題代碼
class Solution {
public:
int minInsertions(string s) {
int n = s.size();
vector<vector<int>> dp(n,vector<int>(n));
for(int i = n - 1;i >= 0;i--)
{
for(int j = i + 1;j < n;j++)
{
if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];
else dp[i][j] = min(1 + dp[i][j - 1],1 + dp[i + 1][j]);
}
}
return dp[0][n - 1];
}
};
最后就順利通過啦！??！文章來源地址http://www.zghlxwxcb.cn/news/detail-741885.html
到了這里，關于【算法|動態(tài)規(guī)劃No.28】leetcode1312. 讓字符串成為回文串的最少插入次數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
