|
哎，国内都在放假，而我还要考试。。。
再总结一道动态规划题目后去看xgboost.
今天是著名的解码方法II
是从解码方法发展过来的题目。下面列一下做这道动归的经典思路：
他比解码方法I多了下面这段描述：
除了 上面描述的数字字母映射方案，编码消息中可能包含 '’ 字符，可以表示从 ‘1’ 到 ‘9’ 的任一数字（不包括
‘0’）。例如，编码字符串 "1" 可以表示 “11”、“12”、“13”、“14”、“15”、“16”、“17”、“18” 或 “19”
中的任意一条消息。对 “1*” 进行解码，相当于解码该字符串可以表示的任何编码消息。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/decode-ways-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处
对当前状态进行讨论:对于当前状态的值只有两种可能，一个是自己独立表达一个数，一个是和前面一个一起表达一个数：就此分类讨论：
class Solution:
def numDecodings(self, s: str) -> int:
n = len(s)
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
if s[i-1]!='*':
if s[i-1]!='0' :
dp[i]+=dp[i-1]
if i>1 and s[i-2]!='0':
if s[i-2]!='*' and int(s[i-2:i]) <=26:
dp[i]+=dp[i-2]
elif s[i-2]=='*':
if int(s[i-1])<=6:
dp[i]+=2*dp[i-2]
else:
dp[i]+=dp[i-2]
else:
dp[i]+=9*dp[i-1]
if i>1 and s[i-2]!='0':
if s[i-2]=='1':
dp[i]+=dp[i-2]*9
elif s[i-2]=='2':
dp[i]+=dp[i-2]*6
elif s[i-2]=='*':
dp[i]+=15*dp[i-2]
return dp[-1]
结果在"*********"这个例子上出错了。还是审题的问题，mod没有加：
class Solution:
def numDecodings(self, s: str) -> int:
MOD=10**9 + 7
n = len(s)
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
if s[i-1]!='*':
if s[i-1]!='0' :
dp[i]+=dp[i-1]
dp[i]=dp[i]%MOD
if i>1 and s[i-2]!='0':
if s[i-2]!='*' and int(s[i-2:i]) <=26:
dp[i]+=dp[i-2]
dp[i]=dp[i]%MOD
elif s[i-2]=='*':
if int(s[i-1])<=6:
dp[i]+=2*dp[i-2]
dp[i]=dp[i]%MOD
else:
dp[i]+=dp[i-2]
dp[i]=dp[i]%MOD
else:
dp[i]+=9*dp[i-1]
dp[i]=dp[i]%MOD
if i>1 and s[i-2]!='0':
if s[i-2]=='1':
dp[i]+=dp[i-2]*9
dp[i]=dp[i]%MOD
elif s[i-2]=='2':
dp[i]+=dp[i-2]*6
dp[i]=dp[i]%MOD
elif s[i-2]=='*':
dp[i]+=15*dp[i-2]
dp[i]=dp[i]%MOD
return dp[-1]
|