第二章：以最小插入次数构造回文串

1312. 让字符串成为回文串的最少插入次数

• dp数组的含义：对字符串s[i...j] （注意这里是两端闭合的）,最少需要进行dp[i][j]次插入才能变成回文串
• base case：左下角三角形为0，对角线处为0（因为自己本身就是回文串，不需要插入）
• 状态转移方程：如果s[i]==s[j]，则dp[i][j]=dp[i+1][j-1],不需要插入操作，直接从dp[i+1][j-1]转移过来即可；如果s[i]!=s[j],则取dp[i+1][j]和 dp[i][j-1]的最小值，插入一次操作即可
• 最终结果保存在dp[0][n-1]处, 我们用从下到上，从左到右的顺序来填dp表

class Solution {
public:
    int minInsertions(string s) {
        int n=s.size();
        vector<vector<int>>dp(n,vector<int>(n,0));
        for (int i = n-2; 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(dp[i+1][j],dp[i][j-1])+1;
            }
        }
        return dp[0][n-1];

    }
};