动态规划

动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

题目

PS:下列题目均来自leetcode中灵神题单

入门

1.1 爬楼梯

70. 爬楼梯

public class Solution {
    public int climbStairs(int n) {
        int[] d = new int[n + 1];
        d[0] = d[1] = 1;
        for (int i = 2; i <= n; i++) {
            d[i] = d[i - 1] + d[i - 2];
        }
        return d[n];
    }
}

746. 使用最小花费爬楼梯

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n=cost.length;
        int[] dp= new int[n+1];
        dp[0]=0;
        dp[1]=0;
        for(int i=2;i<=n;i++){
            dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];

    }
}

2266. 统计打字方案数

"""
思路为构建dp,dp[i]为countTexts第i个数字结尾的所有可能性
那么显然dp[i]=dp[i-1]+dp[-2]+dp[i-3]
和爬楼梯类似，从dp[i-3]一次跳到dp[i],dp[i-2]一次跳到dp[i]这样
再使用乘法原理分割连续相同的字符串
我个考虑的时候
1. 忘记了乘法原理
2. 我考虑的时候想的是dp[i]=dp[i-1]+1+dp[i-2]+1+dp[i-3]+1想的很抽象，不知道为什么我在考虑的时候没有正确理解到dp[i]=dp[i-1]+...里面的dp[i-1]到dp[i]其实是一个类似于楼梯问题，这是一个完整可能结果的一条路径！所以+1是完全没有弄明白
"""
#官方题解
class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        m = 10 ** 9 + 7
        dp3 = [1, 1, 2, 4]   # 连续按多次 3 个字母按键对应的方案数
        dp4 = [1, 1, 2, 4]   # 连续按多次 4 个字母按键对应的方案数
        n = len(pressedKeys)
        for i in range(4, n + 1):
            dp3.append((dp3[i-1] + dp3[i-2] + dp3[i-3]) % m)
            dp4.append((dp4[i-1] + dp4[i-2] + dp4[i-3] + dp4[i-4]) % m)
        res = 1   # 总方案数
        cnt = 1   # 当前字符连续出现的次数
        for i in range(1, n):
            if pressedKeys[i] == pressedKeys[i-1]:
                cnt += 1
            else:
                # 对按键对应字符数量讨论并更新总方案数
                if pressedKeys[i-1] in "79":
                    res *= dp4[cnt]
                else:
                    res *= dp3[cnt]
                res %= m
                cnt = 1
        # 更新最后一段连续字符子串对应的方案数
        if pressedKeys[-1] in "79":
            res *= dp4[cnt]
        else:
            res *= dp3[cnt]
        res %= m
        return res

2466. 统计构造好字符串的方案数

#初始状态定义为1，表示呆在原地？
class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        mi=min(zero,one)
        ma=max(zero,one)
        dp=[0]*(high+1)
        dp[0]=1
        for i in range(1,high+1):
            if i>=one:
                dp[i]=dp[i-one]
            if i>=zero:
                dp[i]+=dp[i-zero]
        return sum(dp[low:]) % (10**9+7)