DP数组的容量要不要+1？

其实，dp数组要不要+1，完全取决于“DP数组”下标代表什么。

简单来说，只有两种情况。我们结合“凑钱”题和经典的“爬楼梯”题来对比一下。

📏 情况一：下标代表“金额/重量/容量”（需要 +1）

场景：背包问题、凑零钱、分割等和子集。
例子：你的目标是凑出11块钱。

为什么要 +1？
因为钱是可以为 0 的。
你的记账本不仅要记录“能不能凑出 11 块”，还要记录“能不能凑出 0 块”、“能不能凑出 1 块”……一直到“能不能凑出 11 块”。

• 如果你写new int[11]：
  • 下标范围是0到10。
  • 最大只能记到 10 块，11 块那个格子根本不存在（越界了）！
• 如果你写new int[11 + 1]：
  • 下标范围是0到11。
  • 正好能记下目标金额 11。

结论：只要你的下标i代表的是**“具体的数值大小”（比如金额、背包重量、台阶数），而且这个数值包含 0**，你就必须+1，因为0也要占一个格子。

🍞 情况二：下标代表“第几个物品/第几步”（通常不用 +1，或者视定义而定）

场景：爬楼梯、打家劫舍、最长递增子序列。
例子：给你 5 个数字[1, 5, 11, 5, 2]，问最长序列是多少。

为什么不用 +1？
因为这里的下标i只是用来遍历数组的。

• 数组本身长度是 5。
• 我们定义dp[i]为“以第 i 个数字结尾的最长序列”。
• 我们只需要算到dp[4]（也就是最后一个数字 2）就结束了。
• 此时dp数组的大小只要和原数组一样大（5）就够了，不需要去记录“第 5 个数字”（因为根本不存在）。

特殊情况（为了偷懒）：
有些人在写“爬楼梯”或者“背包二维数组”时，喜欢故意把数组开大一点（n+1），是为了处理边界更方便。

• 比如爬楼梯，如果开n+1，你可以直接从dp[1]开始算，不用管dp[0]是不是越界。
• 但这属于“为了代码写得爽”，而不是逻辑上的必须。

⚖️ 一张表总结

💡 终极判断口诀

当你拿不准要不要+1时，问自己一个问题：

“我的目标值（比如 11），需不需要作为一个下标存进数组里？”

• 需要（比如凑钱题，我要查dp[11]）：必须 +1。
• 不需要（比如数组题，我只需要算到dp[n-1]）：不用 +1。

在刚才的“分割等和子集”里，我们的目标是凑出target，最后要返回dp[target]，所以必须 +1，否则dp[target]就报错了！