动态规划就是根据子问题的解以得出原问题的解

动态规划的特性

最优子结构

最优子结构规定的是子问题与原问题的关系，即原问题的最优解包含子问题的最优解，将子问题的解进行组合可以得到原问题的解是动态规划可行性的关键，在解题中一般用状态转移方程描述这种组合以及使用剪切粘贴法来证明

重叠子问题

重叠子问题规定的是子问题与子问题的关系，即每次子问题不会生成更多的子问题，重复子问题不是保证解的正确性必须的，但是如果递归求解子问题时，没有出现重复子问题，则没有必要用动态规划，直接普通的递归就可以了

动态规划的实现方法

动态规划的进化过程：暴力递归 -> 记忆化搜索 -> 动态规划

一般的动态规划题目可以通过更加暴力的手段解决，但是时间复杂度不忍直视，dp就是根据题目特性减少重复计算，以时间换空间

算法导论中提供了两种等价的实现方法，一种是带备忘的自顶向下法，一种是自底向上法

题目特点

1，求总数：有多少种方法走到该点、有多少方法选出 k 个数的和是 sum 2，求最大值和最小值 3，求存在性：取石子游戏、提供一些步骤将字母变化 4，求从 m 中选出 n 个问题

如果遇到以上的问题，可以优先考虑使用 dp 来解题

解题步骤

1，最后一步：解题的第一步非常重要，该步骤对应最优子结构。具体操作是设该结果为f(n)，f(n)一定是该问题的最优解，考虑f(n-1)与f(n)的关系，我们找出f(n-1)以及最后一步的选择可以得出答案

可以证明 f(n-1) 必然是该子问题的最优解，可以使用剪切粘贴法来证明，假设 f(n-1) 并不是子问题的最优解，必然可以找到一个更加合适的解，就可以将 f(n-1) 截切掉并且粘贴上该解，因此假设错误

2，转移方程：通过最后一步来列出转移方程

3，边界条件与初始条件：每个题目有不同的要求，在解题的时候注意一下就好

示例

题目：

给你一个下标从 0 开始的 二进制字符串 floor，它表示地板上砖块的颜色。floor[i] = '0' 表示地板上第 i 块砖块的颜色是黑色。floor[i] = '1' 表示地板上第 i 块砖块的颜色是 白色 。同时给你 numCarpets 和 carpetLen 。你有 numCarpets 条黑色的地毯，每一条黑色 的地毯长度都为 carpetLen 块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余白色砖块的数目最小

地毯相互之间可以覆盖。

请你返回没被覆盖的白色砖块的 最少 数目。

思路：

这题就是将 numCarpets 条黑色的地毯铺到合适的位置，那么我们需要关心的参数是 numCarpets，我们需要对地毯进行状态转移，有的同学可以过于考虑 floor，去遍历 floor 字符串，那么解题思路就会变成暴力。此类题目比较复杂，核心思路就是二维动态规划

定义状态：dp[i][j] 表示使用前 i 条地毯覆盖前 j 块砖块后，未被覆盖的白色砖块的最少数量

初始化：dp[0][j] 表示不使用任何地毯时，前 j 块砖块中未被覆盖的白色砖块的数量。可以通过遍历 floor 字符串来计算

状态转移：

1，不使用当前地毯：dp[i][j] = dp[i-1][j] 2，使用当前地毯：dp[i][j] = dp[i-1][max(0, j-carpetLen)] + whiteCount[j] - whiteCount[max(0, j-carpetLen)]

whiteCount[k] 表示前 k 块砖块中白色砖块的数量

最终结果：dp[numCarpets][n]，其中 n 是 floor 的长度

示例代码：

def min_white_tiles(floor, numCarpets, carpetLen):
    n = len(floor)
    
    ## 计算前缀和数组，whiteCount[i] 表示前 i 块砖块中白色砖块的数量
    whiteCount = [0] * (n + 1)
    for i in range(n):
        whiteCount[i + 1] = whiteCount[i] + (1 if floor[i] == '1' else 0)
    
    ## 初始化 DP 数组
    dp = [[float('inf')] * (n + 1) for _ in range(numCarpets + 1)]
    
    ## 不使用地毯的情况
    for j in range(n + 1):
        dp[0][j] = whiteCount[j]
    
    ## 填充 DP 数组
    for i in range(1, numCarpets + 1):
        for j in range(n + 1):
            dp[i][j] = dp[i-1][j]  ## 不使用当前地毯
            if j >= carpetLen:
                dp[i][j] = min(dp[i][j], dp[i-1][j - carpetLen])  ## 使用当前地毯
    
    return dp[numCarpets][n]