LeetCode 413. 等差数列划分思路动态规划滚动变量优化关键定义dp[i] 表示以 nums[i] 结尾的等差子数组个数。状态转移· 若 nums[i] - nums[i-1] nums[i-1] - nums[i-2]则 dp[i] dp[i-1] 1· 因为以 i-1 结尾的每个等差子数组加上 nums[i] 后仍然等差且 [i-2, i-1, i] 这三个元素本身又构成一个新的等差子数组。· 否则 dp[i] 0答案 所有 dp[i] 之和。由于 dp[i] 只依赖 dp[i-1]可用一个变量滚动替代数组空间降到 O(1)。Java 实现classSolution{publicintnumberOfArithmeticSlices(int[]nums){intnnums.length;if(n3)return0;inttotal0;// 所有 dp[i] 之和intcur0;// dp[i-1]for(inti2;in;i){if(nums[i]-nums[i-1]nums[i-1]-nums[i-2]){cur1;totalcur;}else{cur0;}}returntotal;}}复杂度· 时间O(n)一次遍历· 空间O(1)滚动变量测试样例SolutionsnewSolution();System.out.println(s.numberOfArithmeticSlices(newint[]{1,2,3,4}));// 3System.out.println(s.numberOfArithmeticSlices(newint[]{1}));// 0System.out.println(s.numberOfArithmeticSlices(newint[]{1,2,3}));// 1System.out.println(s.numberOfArithmeticSlices(newint[]{1,3,5,7,9}));// 6对 [1,2,3,4]i 差值判断 cur total2 1 1 ✓ 1 13 1 1 ✓ 2 3结果 3对应 [1,2,3]、[2,3,4]、[1,2,3,4]。关键点易错点 说明子数组必须连续 这是「子数组」而非「子序列」DP 才成立长度 3 直接返回 0差值比较 用 nums[i]-nums[i-1] nums[i-1]-nums[i-2]避免溢出可改写为 2*nums[i-1]nums[i]nums[i-2]cur 1 而非 cur dp[i-1] 每延续一次等差数列以 i 结尾的个数比 i-1 多 1另一种写法显式 dp 数组便于理解classSolution{publicintnumberOfArithmeticSlices(int[]nums){intnnums.length;if(n3)return0;int[]dpnewint[n];intans0;for(inti2;in;i){if(nums[i]-nums[i-1]nums[i-1]-nums[i-2]){dp[i]dp[i-1]1;ansdp[i];}}returnans;}}两种写法本质一致面试推荐滚动变量版空间 O(1)。