动态规划-中级-II
1. 解码方式-decode ways
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
从例2可以看出，位置为0的时候为1种，位置为1的时候有{2 2}，{22}两种，而位置为2时，6在[1.9]内，可以构成独立数字，dp[2]=dp[1];又因为26在[10,26]内，其结果又加上dp[0],结果等于dp[2]=dp[1]+dp[0]。
则可以得到转移方程：dp[i]=dp[i-1]+dp[i-2] if s[i]>0 and s[i-1]s[i] in [10,26], 如果只满足一种条件，则加上相应的值。
note:在考虑转移方程时，这里必须保证当前字符>0,且当前字符与前一个字符组成的字符>=10。比如例“01”,dp[0]=0,dp[1]时应该判断，s[1]>=1,s[0]s[1]>=10
初始化dp[0]=1
class Solution:def numDecodings(self, s: str) -> int:num = [i for i in range(1, 27)]if s == '': return 0length = len(s)dp = [1]dp += [1] if int(s[0]) in num else [0]for i in range(2, length + 1):dp += [0]if int(s[i - 1]) in num:dp[i] += dp[i - 1]if int(s[i - 2] + s[i - 1]) >= 10 and int(s[i - 2] + s[i - 1]) <= 26:dp[i] += dp[i - 2]if s[i - 2] == 0 and s[i - 1] == 0: return 0return dp[-1]
2. 三角形路径和
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
问题:给定三角形，找到自顶向下的最小路径和。每一次可以移动到下一行相邻的数字。
分析：很典型的动态规划问题，这里可以建立一个尺寸等于三角形的dp数组，其中dp[i]表示自顶到第i行时的路径和，当i>=2时，由于i=1有两个值，i=2时会有一个重叠值，这里重叠的值可以取最小。最后返回最后一行的min即可。
class Solution:def minimumTotal(self, triangle) -> int:dp=[[triangle[0][0]]]for i in range(1,len(triangle)):for j in range(len(triangle[i])):if j==0:dp.append([dp[i-1][0]+triangle[i][0]])elif j==len(triangle[i])-1:dp[i].append(dp[i-1][-1]+triangle[i][-1])else:dp[i].append(min(dp[i-1][j-1]+triangle[i][j],dp[i-1][j]+triangle[i][j]))return min(dp[-1])
# 这里是构建了DP数组，需要额外的O(n) space。考虑到每次计算时只利用上一行的值，可以不额外构建dp数组，直接在原有数组上进行计算来释放空间。class Solution:def minimumTotal(self, triangle) -> int:for i in range(1,len(triangle)):triangle[i][0]+=triangle[i-1][0]triangle[i][-1]+=triangle[i-1][-1]for j in range(1,len(triangle[i])-1):triangle[i][j]=min(triangle[i-1][j-1]+triangle[i][j],triangle[i-1][j]+triangle[i][j])return min(triangle[-1])
3. 插入与删除
Note:
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
问题：给定非空字符串s和字典wordDict，包含非空单词list，判断s能不能被分割成一个或多个字典单词。
分析：依然使用dp的方法，构建dp数组。考虑一下，如果结果为true，那么从左往右进行匹配的话，s的最后一个字符肯定是在字典中的。那么，可以对dp进行定义，dp[i]表示索引为i的字符是以字典中的单词结尾的。
比如 leetcode, dp[3]=True,因为s[:4] in wordDict. dp[7]=True,因为s[4:] in wordDict且dp[7-len(code)]=True。这样，迭代的比较子串是否在字典中，并对索引i下的dp赋值，如果dp[-1]为True,则表明能够完全分割。
class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:dp=[False]* len(s)for i in range(len(s)):for w in wordDict:if w == s[i-len(w)+1:i+1] and (dp[i-len(w)]==True or i -len(w) == -1):dp[i]=Truereturn dp[-1]