DP遍历避坑：索引遍历 vs 长度遍历，该怎么选？

做动态规划（DP）题时，很多同学都会卡在一个细节上：同样是遍历推导状态，到底该用「索引遍历」还是「长度遍历」？

就像之前聊到的最长递增子序列（LIS）问题，用索引遍历写起来简洁高效，换成长度遍历反而多一层循环、逻辑绕弯，甚至容易写错边界。其实这两种遍历方式没有绝对的好坏，核心只看一个点——你的DP状态定义是什么。

今天就用最通俗的语言，结合具体例题，帮大家理清两种遍历的适用场景，以后遇到DP题再也不用在遍历方式上纠结！

核心判断原则（记牢这一句就够了）

遍历维度的选择，完全由「DP数组的定义」决定，二者必须贴合，否则就是“舍近求远”：

• 如果DP状态是「以第i个元素为结尾/起点」→ 用索引遍历

• 如果DP状态是「长度为L的子序列/子数组」→ 用长度遍历

简单说，索引遍历是“按元素位置推进”，长度遍历是“按子串/子序列长度推进”。下面结合具体场景，逐个拆解。

一、索引遍历：DP题的“主流选择”（90%场景适用）

索引遍历是动态规划中最常用的遍历方式，核心逻辑是“逐个处理每个元素，基于前一个/前几个元素的状态推导当前状态”。它的优势的是逻辑直观、效率高，尤其适合DP状态绑定「元素位置」的场景。

典型场景1：最长递增子序列（LIS）（最具代表性）

这是我们之前讨论的重点，也是索引遍历的经典应用。

✅ DP定义：dp[i] = 以nums[i]为结尾的最长递增子序列长度

✅ 遍历逻辑：外层遍历索引i（从1开始，因为单个元素的子序列长度默认是1），内层遍历i之前的所有索引j（j < i），判断nums[i]是否大于nums[j]，如果是，就更新dp[i] = max(dp[i], dp[j] + 1)。

✅ 为什么不用长度遍历？强行按长度遍历会多一层循环（外层遍历长度L，中层遍历结尾索引i，内层遍历j），时间复杂度从O(n²)升到O(n³)，逻辑绕且容易出错（比如边界容易写成range(1, n)，正确应为range(2, n+1)）。

核心：状态围绕“第i个元素”展开，索引遍历最贴合，写起来最顺手。

典型场景2：打家劫舍（基础DP题）

这道题也是索引遍历的“常客”，状态完全绑定元素位置。

✅ DP定义：dp[i] = 偷到第i间房子时的最大金额

✅ 遍历逻辑：直接遍历索引i（从0或1开始），推导当前状态——偷第i间房子，就只能取dp[i-2] + nums[i]；不偷第i间房子，就取dp[i-1]，二者取最大值即可。

逻辑非常直白，完全不需要考虑“长度”，索引遍历就是最优选择。

典型场景3：最长回文子串（DP解法）

虽然这道题常用中心扩展法，但DP解法依然是索引遍历的典型应用。

✅ DP定义：dp[i][j] = 字符串中从索引i到j的子串是否为回文

✅ 遍历逻辑：外层遍历结束索引i，内层遍历起始索引j（j ≤ i），判断s[i]和s[j]是否相等，再结合中间子串（i-1到j+1）的回文状态，推导dp[i][j]的值。

核心：状态围绕“索引i和j”展开，用索引遍历能精准覆盖所有子串情况。

二、长度遍历：小众但“精准适配”的场景

长度遍历的适用场景比较小众，核心是“问题本身围绕子序列/子数组的长度展开”，此时DP状态需要绑定“长度L”，用长度遍历能让逻辑更清晰，甚至能优化边界判断。

注意：长度遍历通常会比索引遍历多一层循环，效率略低，仅在特定场景下更有优势。

典型场景1：最长重复子数组

需求：找到两个数组中“长度最长且连续”的重复子数组。这道题的核心就是“长度”，用长度遍历更合适。

✅ 可选DP定义：dp[L][i][j] = 以nums1[i]和nums2[j]为结尾、长度为L的子数组是否相等

✅ 遍历逻辑：外层遍历长度L（从1到两个数组中较短的长度），中层遍历nums1的索引i，内层遍历nums2的索引j，判断长度为L的子数组是否完全匹配。

✅ 优势：可以提前终止遍历——一旦某个长度L没有找到匹配的子数组，更长的长度肯定也不会有，能节省一定时间。

典型场景2：分割字符串为回文子串（求最少分割数）

这道题的进阶思路，是先预处理“所有长度的子串是否为回文”，再推导最少分割数，此时长度遍历的优势就体现出来了。

✅ 预处理逻辑：外层遍历子串长度L（从1到字符串长度），内层遍历起始索引i，计算结束索引j = i + L - 1，判断s[i..j]是否为回文，将结果存入二维数组备用。

✅ 优势：先按长度预处理所有回文子串，后续推导分割数时，直接查表即可，逻辑更清晰，避免重复判断。

典型场景3：固定长度的滑动窗口类DP

比如“求长度为k的子数组的最大和（DP版）”，这类问题的核心是“固定长度”，用长度遍历能精准绑定状态。

✅ DP定义：dp[L][i] = 以i为结尾、长度为L的子数组和

✅ 遍历逻辑：外层遍历长度L（到k为止），内层遍历索引i，推导dp[L][i] = dp[L-1][i-1] + nums[i]，最终取L=k时的最大值即可。

三、补充：两种都能用的场景，优先选索引遍历

有些简单的DP问题，两种遍历方式都能实现，但索引遍历几乎总是更优——要么效率更高，要么逻辑更简单。

比如“求数组中每个位置的前缀和”：

• 索引遍历：prefix[i] = prefix[i-1] + nums[i]（O(n)效率，最简洁）

• 长度遍历：prefix[L] = prefix[L-1] + nums[L-1]（本质还是索引遍历，只是变量名换成了L，没有任何优势）

所以，即使两种方式都能用，也优先选索引遍历，避免画蛇添足。

总结：一张表分清两种遍历（建议收藏）

最后想说

其实不用死记硬背场景，只要记住：先写清楚DP数组的定义，遍历方式就自然确定了。

如果你的DP定义里有“第i个元素”，就用索引遍历；如果有“长度为L”，就用长度遍历。

对于大部分同学来说，先把索引遍历练熟，能解决绝大多数DP题；长度遍历作为补充，遇到特定场景再针对性掌握就好。

下次做DP题，不妨先写下DP状态定义，再决定遍历方式——你会发现，很多之前纠结的问题，其实都很简单～