经典题目（3）：把数字翻译成字符串；兑换零钱

题目一描述有一种将字母编码成数字的方式a-1, b-2, ... , z-26。现在给一串数字返回有多少种可能的译码结果数据范围字符串长度满足 0n≤90进阶空间复杂度 O(n)时间复杂度 O(n)方法分类讨论首先排除第一个字符为0的数字串然后排除两个相邻数字中第二个数字是0第一个数字不是1或2的情况。然后构建dp数组对于两个相邻数字中第二个数字是1-9第一个数字是1或者第二个数字是1-6第一个数字是2的情况使用状态转移公式dp[i]dp[i-1]dp[i-2]注意初始化dp数组时每个元素赋值为1因为排除了两种特殊情况后每个位置初始的时候都有一种可能遍历的时候当i等于1时dp[1]dp[0]dp[-1]这其实是一个巧合因为空字符串的时候算一种可能代码class Solution: def solve(self , nums: str) - int: # write code here if not nums: return 0 if nums[0]0: return 0 for i in range(1,len(nums)): if nums[i]0 and (nums[i-1]!1 and nums[i-1]!2): return 0 dp[1]*len(nums) for i in range(1,len(nums)): if nums[i-1]1 and int(nums[i])0: dp[i]dp[i-1]dp[i-2] #初始化的时候i-2-1正好等于1 elif nums[i-1]2 and int(nums[i])0 and int(nums[i])7: dp[i]dp[i-1]dp[i-2] else: dp[i]dp[i-1] return dp[-1]题目二描述给定数组arrarr中所有的值都为正整数且不重复。每个值代表一种面值的货币每种面值的货币可以使用任意张再给定一个aim代表要找的钱数求组成aim的最少货币数。如果无解请返回-1.数据范围数组大小满足 0≤n≤10000 数组中每个数字都满足 0val≤100000≤aim≤5000要求时间复杂度 O(n×aim)空间复杂度 O(aim)。方法先排除aim1的情况然后构建dp数组(aim1)*(aim1)其中dp[0]0, 每一个数字的含义是总金额为i最少需要几张纸币然后两层循环分别遍历dp数组和arr如果arr[j]i, 那么dp[i]min(dp[i],dp[i-arr[j]]1)如果纸币金额小于等于总金额那么dp[总金额]min(dp[总金额],dp[总金额-纸币金额]1)最后比较一下dp数组中的最后一个数字是否为aim1如果不是返回值代码class Solution: def minMoney(self , arr: List[int], aim: int) - int: # write code here if aim1: return 0 #这边是返回最少组成的纸币数 dp[aim1]*(aim1) dp[0]0 #这边要初始化第一个值 for i in range(1,aim1): for j in range(len(arr)): if arr[j]i: #可以相等相等就是dp[0] dp[i]min(dp[i],dp[i-arr[j]]1) return dp[-1] if dp[-1](aim1) else -1