【2021】360编程题回文数变换

[编程题]【2021】360编程题回文数变换

热度指数：733 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

所谓回文数就是一个数字，从左边读和从右边读的结果都是一样的，例如12321。

现在有一个只包含1、2、3、4的数字，你可以通过在任意位置增加一位数字或者删除一位数字来将其变换成一个回文数。但是增加或删除不同数字所需要的代价是不一样的。

已知增加和删除每个数字的代价如下：

增加一个1，代价：100；删除一个1，代价：120。

增加一个2，代价：200；删除一个2，代价：350。

增加一个3，代价：360；删除一个3，代价：200。

增加一个4，代价：220；删除一个4，代价：320。

请问如何通过最少的代价将一个数字变换为一个回文数。当然，如果一个数字本身已经是一个回文数（包括一位数，例如：2），那么变换的代价为0。

输入描述:

单组输入。

输入一个由1、2、3、4组成的正整数，正整数位数<=100位。【提示：采用字符串输入】

输出描述:

输出一个整数，表示将输入数字变换为一个回文数所需的最少代价。

示例1

输入

输出

说明

增加一个1并增加一个2，将输入正整数变为1223221或者2123212，所需代价最小，为：100+200=300。

算法知识视频讲解

Python

牛客120963370号

def get_hui(num):
    a = [0,100,200,360,220]
    b = [0,120,350,200,320]
    n = len(num)
    dp = [[0]*n for i in range(n)]
    dp[0][0]=0  for m in range(2,n+1): for i in range(0,n):
            j = i+m-1  if j>=n: break  if num[i]==num[j]:
                dp[i][j]=dp[i+1][j-1] else:
                dp[i][j]=min(dp[i+1][j]+min(a[int(num[i])],b[int(num[i])]),dp[i][j-1]+min(a[int(num[j])],b[int(num[j])])) return dp[0][n-1]
num='12322' print(get_hui(num))