Leetcode1312: 让字符串成为回文串的最少插入次数

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

【思路】
关键词：动态规划

• 定义：dp[i][j] 在把字符串[i:j]变为回文数所需的最少次数
• 状态更新方程： 分情况
  if s[i]==s[j] 那么无需操作，只需保证内层是回文数
  dp[i][j] = dp[i+1][j-1]
  else
  可以在右边添加，或左边添加
  dp[i][j] = min(dp[i+1][j],dp[i][j-1])+1 ---》这一层的插入操作

【需要注意的】
更新的顺序是斜着遍历，代码写法不记得了

int minInsertions(string s) {
    int n = s.size();
    vector<vector<int>> dp(s.size(), vector<int>(s.size())); //dp全部初始化为0
    for (int l = 2; l <= n; ++l) { //斜着遍历
        for (int i = 0; i <= n - l; ++i) {
            int j = i + l - 1;
            if (s[i] == s[j]) {
                dp[i][j] = dp[i + 1][j - 1];
            }
            else {
                dp[i][j] = min(dp[i + 1][j], dp[i][j - 1])+1;
            }
        }
    }

    return dp[0][n-1];

}