//
// Created by 罗炳国 on 2023/12/15.
//

#ifndef PFJ_CODE035_MININSERTIONS_H
#define PFJ_CODE035_MININSERTIONS_H

#include "commonHeader.h"

/**
 * 1312. 让字符串成为回文串的最少插入次数
 * 给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
 * 请你返回让 s 成为回文串的 最少操作次数 。
 * 「回文串」是正读和反读都相同的字符串。
 * https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/
 * */

class code035_minInsertions {
public:
    /* TODO: 空间压缩 */
    int minInsertions(string s) {

        int N = s.size();
        vector<vector<int>> dp(N, vector<int>(N, 0));

        /*
         * 对角线s[i][i] == 0，表示s[i]到s[i]，需要插入0个字符
         * 对角线右侧紧挨对角线那条线，相同为0，不同为1
         * */
        for (int i = 0; i < N - 1; i++)
            dp[i][i + 1] = s[i] == s[i + 1] ? 0 : 1;

        for (int i = N - 3; i >= 0; i--) {
            for (int j = i + 2; j < N; j++) {
                dp[i][j] = dp[i][j - 1] + 1;
                dp[i][j] = min (dp[i + 1][j] + 1, dp[i][j]);
                if (s[i] == s[j])
                    dp[i][j] = min(dp[i + 1][j - 1], dp[i][j]);
            }
        }

        return dp[0][N - 1];
    }

    void test() {
        string s{"a"};
        int ans = minInsertions(s);
        std::cout << "s:" << s << " ans:" << ans << endl;
        s = "ab";
        ans = minInsertions(s);
        std::cout << "s:" << s << " ans:" << ans << endl;

        s = "leetcode";
        ans = minInsertions(s);
        std::cout << "s:" << s << " ans:" << ans << endl;

    }



};


#endif//PFJ_CODE035_MININSERTIONS_H