接龙数列动态规划的python写法

解题思路:

极简 线性DP-Dotcpp编程社区

dp[]数组长度设置为10，因为接龙数列的每一项均为数字，从1~9，0不需要考虑进去；

dp[]数组的含义：以i结尾的接龙数列的最大长度；

设a为接龙数列的第一个数字，b为最后一个数字；

dp[a]表示已a结尾的接龙数列的最大长度，dp[b]表示以b结尾的最大接龙数列长度

初始都是0，从0开始不断变化；

解释：假设输入5位，分别为11 121 22 12 2023；

打印dp[]数组的结果为：

0 2 3 4 0 0 0 0 0 0 #第一个0不用管，因为前导不含0

仔细推导第三、四便可以看出；

#还有些混乱，后续补充......

注意事项:

设a为接龙数列的第一个数字，b为最后一个数字；

dp[]数组的含义：以i结尾的接龙数列的最大长度；

参考代码:

N =int(input())
dp=[0 for _ in range(10)]
ab = list(map(str,input().split()))
for i in range(N):
   a,b=int(ab[i][0]),int(ab[i][-1])
   dp[b] =max(dp[a]+1,dp[b])#dp[a]为上一个以a结尾的最长接龙数列长度，
length = max(dp)
print(N-length)