LeetCode 1312 Minimum Insertion Steps to Make a String Palindrome

    
        标签：
        
            动态规划问题
        
            LeetCode
        
    发布于：2022-02-20 11:18:34
    编辑于：2022-02-20 13:00:21
    浏览量：1094

概述

https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/

动态规划法（从两侧逼近）

从两头开始，如果一致就 okay，否则的话就补，此时有两个选择，补左边还是右边。

这就是 hard 吗？笑死，秒杀。

class Solution {
public:
    vector<vector<int>> dp;
    string s;
    int minInsertions(string s) {
        this->s = s;
        dp.resize(s.size(), vector<int>(s.size(), -1));
        return helper(0, s.size() - 1);
    }
    
    int helper(int l, int r) {
        if (l >= r) return 0;
        if (dp[l][r] != -1) return dp[l][r];
        if (s[l] == s[r]) {
            dp[l][r] = helper(l+1, r-1);
        } else {
            dp[l][r] = 1 + min(helper(l+1, r), helper(l, r-1));
        }
        return dp[l][r];
    }
};

Links: leetcode-1312-minimum-insertion-steps-to-make-a-string-palindrome