假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。 每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。
例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。 用尽量少的涂色次数达到目标。
[编程题][CQOI2007]涂色PAINT
import sys
num =[]
for line in sys.stdin:
a = line.split()
num.append(a)
try:
string= a[0]
except:
string=num[0][0]
length = len(string)
dp = [[0]*(length+1) for i in range(length+1)]
for i in range(length):
dp[i][i] = 1
for leng in range(1,length+1,1):
for i in range(0,length-leng,1):
ends = leng+i
dp[i][ends] = float('inf')
if string[i] == string[ends]:
dp[i][ends] = min(dp[i+1][ends],dp[i][ends-1])
for j in range(i,leng+i+1,1):
dp[i][ends] = min(dp[i][ends],dp[i][j]+dp[j+1][ends])
print(dp[0][length-1])
发表于 2022-12-15 21:04:24
回复(1)
补充一个python版本
def ans():
s = list(input())
size = len(s)
dp = [[float("inf")] * size for _ in range(size)]
for l in range(size):
for left in range(size):
if l == 0:
dp[left][left] = 1
continue
right = left + l
if right < size:
if s[left] == s[right]:
dp[left][right] = min(dp[left+1][right],dp[left][right-1])
else:
for mid in range(left,right):
dp[left][right] = min(dp[left][right], dp[left][mid] + dp[mid+1][right])
else:
break
print(dp[0][size-1])
ans()
发表于 2021-11-03 22:44:39
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
