初学算法打卡第一天:入门 DP问题
一:力扣 70. 爬楼梯
假设你正在爬楼梯。需要n阶你才能到达楼顶。
每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？
思路:将大问题拆成小问题
可以从前往后或者从后往前思考,我习惯从后往前思考这类问题,当我们已经到达了终点,那么到达终点之前有两种情况:爬了一步台阶或者两步台阶.因此可以利用递归来完成解答fun(n) = fun(n-1)+fun(n-2),只需要考虑边界问题,fun(n)代表爬到第n个台阶有这么多爬法,那么当n<=0时的爬法应该为0,同时可以利用哈希表存储,防止重复运算.
class Solution: def climbStairs(self, n: int) -> int: cache = [-1] * n def fun(i): if i<=0: return 0 if i==1: return 1 if i==2: return 2 if cache[i-1]!=-1: return cache[i-1] cache[i-1] = fun(i-2)+fun(i-1) return fun(i-2)+fun(i-1) return fun(n)优化:递归转递推
递推即从前往后思考问题,可以定义一个长度为n+1的数组dfs[],其中dfs[i]代表到达第i个台阶的方案数,这类方法最难的就是边界问题,到达地面即dfs[0]的方案数可以设为1,同时将dfs[1]也初始化,防止dfs[i-2]的边界溢出问题.
class Solution: def climbStairs(self, n: int) -> int: dfs = [0]*(n+1) dfs[0] = dfs[1] = 1 for i in range(2,n+1): dfs[i] = dfs[i-1]+dfs[i-2] return dfs[n]递推优化,在实现递推的过程中,可以发现,每次的台阶计算方案数都只需要前两个台阶的方案数相加,因此还可以对上面的代码进行空间优化,只需要常数个空间即可完成计算.
class Solution: def climbStairs(self, n: int) -> int: f0 = f1 =1 for i in range(2,n+1): newf = f1 f1 = newf+f0 f0 = newf return f1二:746. 使用最小花费爬楼梯
class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: # 递归写法 lenth = len(cost) @cache def fun(n): if n==0 or n==1 or n<0: return 0 return min(fun(n-1)+cost[n-1],fun(n-2)+cost[n-2]) return fun(lenth) # 递推写法 n = len(cost) dfs = [0]*n for i in range(2,n): dfs[i] = min(dfs[i-1]+cost[i-1],dfs[i-2]+cost[i-2]) return min(dfs[n-1]+cost[n-1],dfs[n-2]+cost[n-2]) #递推优化 n = len(cost) d0 = d1 =0 for i in range(2,n): newf = min(d0+cost[i-2],d1+cost[i-1]) d0 = d1 d1 = newf return min(d1+cost[n-1],d0+cost[n-2])三:3693. 爬楼梯 II
class Solution: def climbStairs(self, n: int, costs: List[int]) -> int: f1 = f2 = f3 = 0 for i in range(0,n): newf = costs[i]+ min(f3+1,f2+4,f1+9) f1=f2 f2=f3 f3=newf return f3四:377. 组合总和 Ⅳ
class Solution: def combinationSum4(self, nums: List[int], target: int) -> int: hash1 = [-1]*(target+1) def fun(i): ans = 0 if i==0: return 1 if i<0: return 0 for x in nums: if i-x<0: continue if hash1[i-x]!=-1: ans += hash1[i-x] else: ans += fun(i-x) hash1[i] = ans return ans return fun(target)五:2466. 统计构造好字符串的方案数
class Solution: def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int: MOD = 1_000_000_007 # 递归 @cache def fun(i): if i<0: return 0 if i==0: return 1 return (fun(i-zero)+fun(i-one)) % MOD ans = 0 for i in range(low,high+1): ans= (ans+fun(i)) % MOD return ans # 递推 arr1 = [1]+[0]*high for i in range(1,high+1): if i>=zero: arr1[i] = (arr1[i]+arr1[i-zero])%MOD if i>=one: arr1[i] = (arr1[i]+arr1[i-one])%MOD ans = 0 for i in range(low,high+1): ans = (ans+arr1[i])%MOD return ans六:2266. 统计打字方案数
这个题目稍微难一些,但其核心问题仍然是爬楼梯问题,一个连续的字符串,需要统计它的不同情况的组合数.我们先将问题拆成相同连续子串有多少种组合情况,如果是连续n个相同的字符,那么它有多少种组合方式呢? 可以把这个问题也想成爬楼梯问题,一共n层楼梯,每次可以爬1~3次(7和9的情况单独判断),可以用递归来判断次数,fun(n) = fun(n-1)+fun(n-2)+fun(n-3)这个是连续相等的子字符串的可能个数,不同的连续子字符串之间的可能性是互斥的,所以结果要相乘,同时不要忘记字符串的最后一个,要单独判断
class Solution: def countTexts(self, pressedKeys: str) -> int: MOD = 1_000_000_007 @cache def fun(i,x): if i<0: return 0 if i==0: return 1 if x==1: return (fun(i-1,x)+fun(i-2,x)+fun(i-3,x))%MOD else : return (fun(i-1,x)+fun(i-2,x)+fun(i-3,x)+fun(i-4,x))%MOD num = 0 ans=1 lenth = 0 index = pressedKeys[0] for i in pressedKeys: lenth+=1 if i!=index or lenth==len(pressedKeys): if lenth==len(pressedKeys) and i==index: index=i num+=1 if index=="7" or index =="9": ans = (ans*fun(num,0))%MOD else: ans = (ans*fun(num,1))%MOD num=0 index = i num+=1 return ans