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

本文主要是介绍牛客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,取最小+1dp[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 := 0if 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 //左边和下边选最小的+1if 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];
}