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

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
== 516 最长回文子序列

  1. //二维dp，时空On^2
  2. // 和516换汤不换药
  3. func minInsertions(s string) int {
  4.     n := len(s)
  5.     dp := make([][]int, n+1)
  7.     for i := range dp {
  8.         dp[i] = make([]int, n+1)
  9.         //dp[i][i] = 1                          //少一个初始化 dp[i][i] = 1
  10.     }
  11.     for i := n-1; i >= 0; i-- {                 //倒序遍历
  12.         for j := i+1; j < n; j++ {
  13.             if s[i] == s[j] {
  14.                 dp[i][j] = dp[i+1][j-1]         //不用插入，本身就是回文串  = 2 + dp[i+1][j-1]
  15.             } else {
  16.                 dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1      //插一个试试？
  17.             }
  18.         }
  19.     }
  20.     return dp[0][n-1]
  21. }
  22. func min(x int, y int) int {
  23.     if x > y {
  24.         return y
  25.     }
  26.     return x
  27. }
//一维，压缩空间
func minInsertions(s string) int {
    n := len(s)
    dp := make([]int, n)

    for i := n-2; i >= 0; i-- {
        prev := 0

        for j := i+1; j < n; j++ {
            temp := dp[j]
            if s[i] == s[j] {
                dp[j] = prev
            } else {
                dp[j] = min(dp[j], dp[j-1]) + 1
            }
            prev = temp
        }
    }
    return dp[n-1]
}


func min(x, y int) int {
    if x < y { 
        return x 
    }
    return y
}