LeetCode 413. 等差數(shù)列劃分思路動(dòng)態(tài)規(guī)劃滾動(dòng)變量?jī)?yōu)化關(guān)鍵定義dp[i] 表示以 nums[i] 結(jié)尾的等差子數(shù)組個(gè)數(shù)。狀態(tài)轉(zhuǎn)移· 若 nums[i] - nums[i-1] nums[i-1] - nums[i-2]則 dp[i] dp[i-1] 1· 因?yàn)橐?i-1 結(jié)尾的每個(gè)等差子數(shù)組加上 nums[i] 后仍然等差且 [i-2, i-1, i] 這三個(gè)元素本身又構(gòu)成一個(gè)新的等差子數(shù)組。· 否則 dp[i] 0答案 所有 dp[i] 之和。由于 dp[i] 只依賴 dp[i-1]可用一個(gè)變量滾動(dòng)替代數(shù)組空間降到 O(1)。Java 實(shí)現(xiàn)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;}}復(fù)雜度· 時(shí)間O(n)一次遍歷· 空間O(1)滾動(dòng)變量測(cè)試樣例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對(duì) [1,2,3,4]i 差值判斷 cur total2 1 1 ? 1 13 1 1 ? 2 3結(jié)果 3對(duì)應(yīng) [1,2,3]、[2,3,4]、[1,2,3,4]。關(guān)鍵點(diǎn)易錯(cuò)點(diǎn) 說(shuō)明子數(shù)組必須連續(xù) 這是「子數(shù)組」而非「子序列」DP 才成立長(zhǎng)度 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] 每延續(xù)一次等差數(shù)列以 i 結(jié)尾的個(gè)數(shù)比 i-1 多 1另一種寫法顯式 dp 數(shù)組便于理解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;}}兩種寫法本質(zhì)一致面試推薦滾動(dòng)變量版空間 O(1)。