本文由 ChatGPT 生成，方便复习用。

观察到有一些题目，棋盘明明是 m*n，做 dp 的时候，却要(m+1) * (n+1) 个空间，于是总结几道题如下。

动态规划问题中经常会用到 n+1 和 k+1 的 dp 数组，以便更方便地处理边界情况。

我将给你几个例子，以加深理解：

1. 零钱兑换问题：

问题描述：给定不同面额的硬币 coins 和一个总金额 amount，计算出可以凑成总金额所需的最少硬币数量。如果无法凑成，返回 -1。

在这个问题中，我们可以使用 dp 数组来记录每个金额对应的最少硬币数量。创建 dp 数组时，通常会多加一项，例如 dp[amount + 1]，以处理金额为 0 的情况。

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

2. 最长递增子序列问题：

问题描述：给定一个无序的整数数组，找到其中最长上升子序列的长度。

在这个问题中，我们通常使用 dp 数组来记录以每个元素结尾的最长上升子序列的长度。创建 dp 数组时，也会多加一项，例如 dp[n]，以处理空序列的情况。

def lengthOfLIS(nums):
    n = len(nums)
    dp = [1] * n

    for i in range(n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp) if n > 0 else 0

3. 走棋盘问题：

问题描述：在一个 m x n 的棋盘上，从左上角走到右下角，每次只能向右或向下移动一步，求所有可能的路径数量。

在这个问题中，我们可以使用 dp 数组来记录从起点到每个格子的路径数量。创建 dp 数组时，通常会多加一行和一列，例如 dp[m+1][n+1]，以处理起点和终点的情况。

def uniquePaths(m, n):
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    dp[1][1] = 1

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if i > 1:
                dp[i][j] += dp[i - 1][j]
            if j > 1:
                dp[i][j] += dp[i][j - 1]

    return dp[m][n]

4. 分割等和子集问题：

问题描述：给定一个只包含正整数的非空数组 nums，判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

在这个问题中，我们可以使用 dp 数组来记录能否从前 i 个元素中选择若干个元素，使得它们的和等于 j。创建 dp 数组时，通常会多加一行和一列，例如 dp[n+1][target+1]，以处理空数组和空目标的情况。

def canPartition(nums):
    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False

    target = total_sum // 2
    n = len(nums)

    dp = [[False] * (target + 1) for _ in range(n + 1)]
    dp[0][0] = True

    for i in range(1, n + 1):
        for j in range(target + 1):
            if j >= nums[i - 1]:
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
            else:
                dp[i][j] = dp[i - 1][j]

    return dp[n][target]

5. 房屋偷盗问题（原问题）：

问题描述：小偷想要从一排房屋中偷取现金，但不能偷相邻的房屋。每个房屋中有一定数量的现金，小偷的目标是偷取到最多的现金，但不能触发警报。

在这个问题中，我们使用了 (n + 1) x (k + 1) 的 dp 数组，以处理偷取 0 间房屋和偷取至少 k 间房屋的情况。

def minStealing(nums, k):
    n = len(nums)
    dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 0

    for i in range(1, n + 1):
        for j in range(1, k + 1):
            dp[i][j] = min(dp[i - 1][j], dp[i - 2][j - 1] + nums[i - 1])

    return dp[n][k]

希望这些例子有助于更好地理解如何使用 n+1 和 k+1 的 dp 数组来处理不同类型的动态规划问题。

要注意的是：

dp = [[0] * (n + 1) for _ in range(m + 1)] 这种构建，要用 for。

在构建二维数组时，使用 * (m + 1) 的方式可以创建 m+1 个相同的列表对象的引用，这意味着所有子列表都指向同一个列表对象。这样的话，如果你修改其中一个子列表的值，所有子列表都会发生变化，这通常不是我们想要的行为。

例如，如果你使用 dp = [[0] * (n + 1)] * (m + 1) 来创建 dp 数组，然后修改 dp[0][0] 的值，那么 dp 数组的所有元素都会变为相同的值，因为它们都引用同一个子列表。

为了避免这种问题，通常建议使用列表推导式或循环来创建二维数组，确保每个子列表都是独立的对象，不会相互影响。例如，使用 dp = [[0] * (n + 1) for _ in range(m + 1)] 就可以确保每个子列表都是独立的，不会相互影响。