[leetcode] 动态规划 - 入门之爬楼梯与打家劫舍

本篇是动态规划的入门篇，分别是爬楼梯与打家劫舍两大类。这两大类的划分取自leetcode灵神的题单

一、爬楼梯

70. 爬楼梯 [Simple]
746. 使用最小花费爬楼梯 [Simple]
377. 组合总和 Ⅳ [Medium]
2466. 统计构造好字符串的方案数 [Medium]
2266. 统计打字方案数 [Medium]
2533. 好二进制字符串的数量 [Medium]

# 70. 爬楼梯
class Solution:
    def climbStairs(self, n: int) -> int:
    
    	# 1. 创建f数组
        f = [1] + [0]*n
        
		# 2. 枚举阶跃阶数
        nums = [1,2]
        
        # 3. 状态转移方程，求和，当前i的状态等于所有能够跃迁过来的上一个状态的和
        for i in range(1, n+1):
            f[i] = sum(f[i-x] for x in nums if i>=x)
           
        # 4. 返回最后一个状态
        return f[n]

### 优化空间
class Solution:
    def climbStairs(self, n: int) -> int:
    	# f_1表示f[i-1], f_2表示f[i-2]
        f_2 = f_1 = 1
        for i in range(2, n+1):
            f = f_1 + f_2
            f_2 = f_1
            f_1 = f
        return f_1

爬楼梯这道题是这类题目的模板题，第一种解法是通用解法一共四步。第一步是创建状态f数组，f[0]初始化为1，因为后面的状态都要从它迁移过来。第二步是枚举阶跃阶数，这步很重要，这类题目解法都相同，唯一不同的就是这一步，要根据题目的信息抽取出所有的阶跃阶数。第三步是计算状态转移方程，这一步这类题目都一样。第四步是返回最后一个状态值。
第二种解法是优化空间，用两个变量不断地更新前两个状态值，从而省去了创建f数组。但是不同题目需要仔细考虑临时变量的更替，不如第一种方法套模板来的方便。

# 377. 组合总和 Ⅳ
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        
        f=[1]+[0]*target
        
        for i in range(1,target+1):
            f[i]=sum(f[i-x] for x in nums if i>=x)
        return f[target]

这题题目直接提供了阶跃阶数的数组，直接套用模板即可。另外，这题如果用优化空间的方法就会不太好写，需要对nums中的每个值都要对应创建一个变量去更新。

# 2466. 统计构造好字符串的方案数
MOD = 10**9+7
class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
    
        f = [1]+[0]*high

        nums = [zero, one]

        for i in range(1,high+1):
            f[i] = sum(f[i-x] for x in nums if i>=x) % MOD
        return sum(f[low:]) % MOD

这题本质就是爬楼梯，只是需要从题目中抽取出阶跃阶数zero和one。

# 2266. 统计打字方案数
MOD=10**9+7

f=[1]+[0]*100000
g=[1]+[0]*100000
fnums=[1,2,3]
gnums=[1,2,3,4]
for i in range(1,100001):
    f[i]=sum(f[i-x] for x in fnums if i>=x)%MOD
    g[i]=sum(g[i-x] for x in gnums if i>=x)%MOD

class Solution:
    def countTexts(self, pressedKeys):

        four=set(['7','9'])
        ans=1
        for ch,s in groupby(pressedKeys):
            m=len(list(s))
            ans=(ans*(g[m] if ch in four else f[m]))%MOD
        return ans

这题万变不离其宗，只是有两套阶跃阶数，分别计算。

二、打家劫舍

未完