我们可以把数组类 DP 的规律和常见题型总结为以下几种大类：

一、 规律分类：你面对的是哪种“数组问题”？

1. 元素本身就是“价值/权重”类型（如最大子数组和、打家劫舍）

• 特点：数组里的每个数字代表了某种权重（比如正负收益、金钱、分数），题目要求求出某种最优组合。
• 核心逻辑：元素带权，我们需要通过“选或不选”、“接上或另起炉灶”来做决策。
• 经典例子：
• 最大子数组和：数字有正有负，负数会把和拖下水，所以要权衡是“接上前段”还是“另起炉灶”。
• 打家劫舍：每个房子里有不同金额的钱（权重），相邻不能偷，要在权衡中求最大收益。

2. 数组只充当“坐标/阶梯”类型（如爬楼梯、不同路径）

• 特点：数组本身没有复杂的权重，或者数组下标仅仅代表位置、步数、索引。每个位置的值是恒定的（比如每次只能走 1 步或 2 步）。
• 核心逻辑：我们关心的不是数组里的数字有多大，而是“到达第 $i$ 个位置一共有多少种走法”或者“到达这里的最小代价是多少”。
• 经典例子：
• 爬楼梯：数组索引代表楼梯的阶数，每一阶没有权重的概念，我们求的是到达第 $n$ 阶的总方案数。

3. 两个数组/字符串的匹配类型（如最长公共子序列、编辑距离）

• 特点：题目给你两个数组或字符串（比如 text1 和 text2），需要找出它们之间的某种对应关系。
• 核心逻辑：状态通常定义为二维的 dp[i][j]，表示“第一个数组的前 $i$ 个元素”和“第二个数组的前 $j$ 个元素”的最优解。

二、 为什么有的直接取 dp[n-1]，有的要取 max(dp)？

正如你前面所问的，这和数组中权重的分布以及状态定义息息相关：

• 如果求的是“全局累积/终点状态”（如爬楼梯、路径问题、打家劫舍）：
  终点就是全局的终极目标，所以答案自然藏在最后一个状态里，直接取 dp[n-1]。
• 如果求的是“局部最优解的集合”（如最大子数组和、最长递增子序列 LIS）：
  由于最优解可能在数组的任意一个地方戛然而止（比如最大和的一段正好在中间），终点不一定是全局最优解结束的地方。因此，我们需要把每个位置作为结尾的结果全部算出来，最后用 max(dp) 在所有局部最优解中挑出最大值。