经典题目（3）：把数字翻译成字符串；兑换零钱
题目一：
描述
有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。
现在给一串数字，返回有多少种可能的译码结果
数据范围：字符串长度满足 0<n≤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]题目二：
描述
给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
如果无解，请返回-1.
数据范围：数组大小满足 0≤n≤10000， 数组中每个数字都满足 0<val≤10000，0≤aim≤5000
要求：时间复杂度 O(n×aim)，空间复杂度 O(aim)。
方法：
先排除aim<1的情况
然后构建dp数组(aim+1)*(aim+1)，其中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数组中的最后一个数字是否为aim+1，如果不是，返回值
代码：
class Solution: def minMoney(self , arr: List[int], aim: int) -> int: # write code here if aim<1: return 0 #这边是返回最少组成的纸币数 dp=[aim+1]*(aim+1) dp[0]=0 #这边要初始化第一个值 for i in range(1,aim+1): 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]<(aim+1) else -1