C++ 解法, 执行用时: 10ms, 内存消耗: 408KB, 提交时间: 2022-07-17

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return int整型
     */
    int minInsert(string str) {
        // write code here
        int n=str.size();
        vector<int> dp(n);
        for(int i=n-1;i>=0;--i){
            int pre=0;
            for(int j=i+1;j<n;++j){
                int cur=dp[j];
                if(str[i]==str[j]) dp[j]=pre;
                else dp[j]=min(dp[j],dp[j-1])+1;
                pre=cur;//还是之前i-1的！！！
            }
        }
        return dp[n-1];
    }
};

C++ 解法, 执行用时: 11ms, 内存消耗: 436KB, 提交时间: 2022-08-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return int整型
     */
    int minInsert(string str) {
        // write code here
        int n=str.size();
        vector<int> dp(n);
        for(int i=n-1;i>=0;--i)
        {
            int pre=0;
            for(int j=i+1;j<n;++j)
            {
                int cur=dp[j];
                if(str[i]==str[j])
                    dp[j]=pre;
                else
                    dp[j]=min(dp[j],dp[j-1])+1;
                pre=cur;
            }
        }
        return dp[n-1];
    }
};

C++ 解法, 执行用时: 17ms, 内存消耗: 13872KB, 提交时间: 2022-07-14

class Solution {
  public:
    int minInsert(string str) {
        int h = str.size();
        int a[h][h];
        for (int i = 0; i < h; i++) {
            a[i][i] = 0;
        }
        for (int i = h - 2; i >= 0; i--) {
            for (int j = i + 1; j < h; j++) {
                if (str[i] == str[j]) {
                    a[i][j] = a[i + 1][j - 1];
                } else a[i][j] = min(a[i + 1][j], a[i][j - 1]) + 1;
            }
        }
        return a[0][h - 1];
    }
};

C++ 解法, 执行用时: 17ms, 内存消耗: 13984KB, 提交时间: 2022-04-27

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return int整型
     */
    int minInsert(string str) {
        // write code here
       int n=str.size();
       int a[n][n];
        for(int i=0;i<n;i++){
            a[i][i]=0;
        }
        for(int i=n-2;i>=0;i--){
            for(int j=i+1;j<n;j++){
                if(str[i]==str[j]){
                    a[i][j]=a[i+1][j-1];
                }
                else a[i][j]=min(a[i+1][j],a[i][j-1])+1;
            }
        }
       return a[0][n-1];
    }
};

C++ 解法, 执行用时: 19ms, 内存消耗: 15876KB, 提交时间: 2022-07-05

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return int整型
     */
     
    int minInsert(string str) {
        // write code here
        int n = str.length();
        if(n<=1)
            return 0;
        vector<vector<int>> dp(n,vector<int>(n,0));
        for(int i=n-1;i>=0;i--)
        {
            dp[i][i] = 1;
            for(int j=i+1;j<n;j++)
            {
                if(str[i]==str[j])
                {
                    dp[i][j] = dp[i+1][j-1] + 2;//可能为0
                }
                else
                {
                    dp[i][j] = max(dp[i][j-1],dp[i+1][j]);
                }
            }
        }
        
        return n- dp[0][n-1];        
    }
};