SPOJ迭代动态规划
SPOJ迭代动态规划
提问于 2013-11-26 13:35:16
我能够用递归的DP来解决标题中给出的问题，但得到了TLE。这是因为输入字符串可以有大约5000位数，这导致了大量的子函数调用，而我的程序无法计算结果，甚至在我的计算机上也是如此。
问题如下：标码
我的解决办法如下：
import sys
def chk(word):
if word[0] == '0':
return 0
if int(word) < 27 and int(word) > 0:
return 1
else:
return 0
def dp(line):
if len(line) > 2:
return chk(line[0])*dp(line[1:]) + chk(line[:2])*dp(line[2:])
elif len(line) > 1:
return chk(line[0])*dp(line[1]) + chk(line)
else:
return chk(line)
line = sys.stdin.readline().strip()
while line != '0':
print dp(line)
line = sys.stdin.readline().strip()搜索互联网可以得到以下解决方案：
1)初始化大小为0的N数组，元素0为1 2)遍历所有元素 3)如果是有效的单数数字，将前一个元素的值复制到当前元素(DPi = DPi-1) 4)如果它是一个有效的两位数，将前一个元素的值添加到当前元素(DPi += DPi-2) 一行: DPi = DPi-1 {如果有效个位数}+ DPi-2 {如果当前和以前的元素构成有效的两位数字}
我不确定我是否在做同样的事情，因为我无法理解上面的方法，或者是否有办法将我的递归方法转换为迭代。
回答 2
Stack Overflow用户
回答已采纳
发布于 2013-11-26 13:48:54
该算法采用动态规划的方法。
它只是从左到右扫描代码串。
随着字符串长度的增加，可能性的数量也会增加。
每一个新的数字可以有两种可能性。如果它是一个有效的数字，那么新的可能性数至少等于前一个数字的可能性。
另外，如果新的数字和prev-位数使数字>= 11和<= 26，那么可能性的数量就会增加(可能达到I-2)。
Example if the number is 2134
A[0] = 1.
second digit is 1. Hence A[1] is at least = A[0] = 1.
Also, 21 can make a valid character code as well.
Hence, A[1] becomes 1 + 1 = 2.
The two strings possible upto A[1] are 2,1 and 21.
Third digit is 3. Hence A[2] is at least = A[1] = 2.
Also, 13 can make a valid character code.
Hence additional possibilities can result if we consider 13 as a single character = A[2].
Hence A[3] = 2 + 1 = 3 ({2,1,3}, {21,3}, {2,13})
Simililarly for A[4].Stack Overflow用户
发布于 2013-11-26 13:45:42
2非常小的修改(不会提高效率，但更多的丙酮和更好)
def chk(word):
if word[0] == '0':
return 0
elif 0 < int(word) < 27: # notice the elif & multiple comparisons
return 1
else:
return 0页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20218546
复制相关文章
相似问题
腾讯云开发者
