牛客NC376 变回文串的最少插入次数【困难 动态规划，回文 C++/Java/Go/PHP 高频】力扣同一道题1312

题目

题目链接：
https://www.nowcoder.com/practice/bae2652b4db04a438368238498e4c13e

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

思路

参考答案C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return int整型
     */
    int minInsert(string str) {
        //动态规划，详细注释看Go答案
        int n = str.size();
        vector<vector<int>> dp(n, vector<int>(n ));

        for (int i = 0; i < n - 1; i++) {
            dp[i][i + 1] = str[i] == str[i + 1] ? 0 : 1;
        }

        for (int i = n - 3; i >= 0; i--) {
            for (int j = i + 2; j < n; j++) {
                int cur = dp[i][j - 1];
                if (dp[i + 1][j] < cur) {
                    cur = dp[i + 1][j];
                }
                dp[i][j] = cur + 1;

                if (str[i] == str[j]) {
                    cur = dp[i + 1][j - 1];
                    if (dp[i][j] > cur) {
                        dp[i][j] = cur;
                    }
                }
            }
        }
        return dp[0][n - 1];
    }
};

参考答案Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return int整型
     */
    public int minInsert (String str) {
        //https://blog.csdn.net/xiaolu567/article/details/125906480
        //动态规划
        int n = str.length();
        int[][] dp = new int[n][n];

        //填充倒数第二行开始的对角线:dp[i][i+1]
        //第一条dp[i][i]对应的对角线不用填，因为都是0，即插入0次，因为是每个字符自己
        for (int i = 0; i < n - 1 ; i++) {
            dp[i][i + 1] = str.charAt(i) == str.charAt(i + 1) ? 0 : 1;
        }

        //从下往上，倒数第三条对角线开始填dp[i][i+2]
        for (int i = n - 3; i >= 0 ; i--) {
            for (int j = i + 2; j < n ; j++) {
                //自己的左边left和下边bottom,取最小+1
                dp[i][j] = Math.min(dp[i][j - 1], dp[i + 1][j]) + 1;
                if (str.charAt(i) == str.charAt(j)) {
                    //如果相当，自己和左下方对比，取最小
                    dp[i][j] = Math.min(dp[i][j], dp[i + 1][j - 1]);
                }
            }
        }

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

参考答案Go

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param str string字符串
 * @return int整型
 */
func minInsert(str string) int {
	//https://blog.csdn.net/xiaolu567/article/details/125906480
	//动态规划
	n := len(str)
	dp := make([][]int, n)

	//第一条对角线dp[i][i]不用填，都是0
	//填充第二条对角线，dp[i]i+1]
	dp[0] = make([]int, n)
	for i := 0; i < n-1; i++ {
		dp[i+1] = make([]int, n)
		cur := 0
		if str[i] != str[i+1] {
			cur = 1 //i和i+1位置不相等，那么要插入一个后，i和i+1位置变成回文
		}
		dp[i][i+1] = cur
	}

	//第一条对角线，第二条对角线都处理了
	//接下来从第三条对角线开始处理，从下往上处理
	for i := n - 3; i >= 0; i-- {
		for j := i + 2; j < n; j++ {
			cur := dp[i][j-1]
			if cur > dp[i+1][j] {
				cur = dp[i+1][j]
			}

			dp[i][j] = cur + 1 //左边和下边选最小的+1

			if str[i] == str[j] {
				if dp[i+1][j-1] < dp[i][j] {
					dp[i][j] = dp[i+1][j-1] //如果i位置和j位置相等，那么自己和左下角比较，谁小取谁
				}
			}
		}
	}
	return dp[0][n-1]
}

参考答案PHP

<?php


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @return int整型
 */
function minInsert( $str )
{
     //https://blog.csdn.net/xiaolu567/article/details/125906480
    //动态规划
    //详细注释看go答案
    $n = strlen($str);
    $dp =[];
    for($i=0;$i<$n-1;$i++){
        $dp[$i][$i+1] = $str[$i]==$str[$i+1]?0:1;
    }

    for($i=$n-3;$i>=0;$i--){
        for($j=$i+2;$j<$n;$j++){
            $cur =$dp[$i][$j-1];
            if($cur > $dp[$i+1][$j]){
                $cur = $dp[$i+1][$j];
            }
            $dp[$i][$j] = $cur+1;

            if($str[$i]==$str[$j]){
                $cur = $dp[$i+1][$j-1];
                if($dp[$i][$j] > $cur){
                    $dp[$i][$j] = $cur;
                }
            }
        }
    }
    if($dp[0][$n-1] ==null) return 0;
    return $dp[0][$n-1];
}