动态规划五部

/* 动态规划五部曲：

• 1.确定dp[i]的下标以及dp值的含义： 爬到第i层楼梯，有dp[i]种方法；
• 2.确定动态规划的递推公式：dp[i] = dp[i-1] + dp[i-2];
• 3.dp数组的初始化：因为提示中，1<=n<=45 所以初始化值，dp[1] = 1, dp[2] = 2;
• 4.确定遍历顺序：分析递推公式可知当前值依赖前两个值来确定，所以递推顺序应该是从前往后；
• 5.打印dp数组看自己写的对不对；

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
思路：动态规划
当我们最后爬到楼顶时可能是一步，也可能是两步，我们列出f(x)=f(x−1)+f(x−2)，
我们可以知道实际上爬到x层的方案就是爬到x-1层和x-2层的方案之和。
我们要讨论其中的边界值，爬到0级是一种方案，爬到1级只有一种方案，
则F[0]=1,F[1]=1

题目

给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：

将 ‘0’ 在字符串末尾添加 zero 次。
将 ‘1’ 在字符串末尾添加 one 次。
以上操作可以执行任意次。

如果通过以上过程得到一个 长度 在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为 好 字符串。

请你返回满足以上要求的 不同 好字符串数目。由于答案可能很大，请将结果对 109 + 7 取余 后返回。

分析

该题简单来说就是爬楼梯的换皮游戏。即是最后一次可以添加0也可以添加1，我们还可以列出
f[x]=f[x-zero]+f[x-one]
方程的意思是长度为i的字符串，可以由长度为i-one的字符串+one个1构成，也可以由长度为i-zero的字符串+zero个0构成。
class Solution:

def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
    MOD = 10 ** 9 + 7
    f = [1] + [0] * high  # f[i] 表示构造长为 i 的字符串的方案数，其中构造空串的方案数为 1,
    for i in range(1, high + 1):
        if i >= one:  f[i] = (f[i] + f[i - one]) % MOD
        if i >= zero: f[i] = (f[i] + f[i - zero]) % MOD
    return sum(f[low:]) % MOD