求一個數組中等差遞減區間個數，等差數列必須是連續的。?
Example:
A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

分析：用動態規劃解決問題的關鍵是找到每個問題的核心公式，并且知道如何存表。例如本題，我們需要一個存儲總數的變量，和一個存儲差量的變量。
什么是等差數列？ A[i]-A[i-1]=A[i-1]-A[i-2]

#include<iostream>//數組長大于3 //dp[i] 表示到i位置時，子數組的個數 //數組中等差遞增區間個數 ,等差數列要是連續的 class Solution { public:int numberOfArithmeticSlices(int a[]) {int res = 0, n = 5;int dp[10] = {0};for(int i = 2; i < n; i++){if(a[i] - a[i-1] == a[i-1] - a[i-2])dp[i] = dp[i - 1] + 1;std::cout << res << "," << dp[i] << std::endl;res += dp[i];}return res;} };int main(){int a[] = {1, 2, 3, 4, 5};Solution s;int n = s.numberOfArithmeticSlices(a);std::cout<< "n=" << n << std::endl; }

? 打印：

??0,1
?1,2
?3,3
?n=6

???//? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? dpi ?res
// i = 2 ? 123? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1 ? 1
// i = 3 ? 123 234 1234? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?2 ? 3
// i = 4 ? 123 234 345 1234 2345 12345? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 3 ? 6
// i = 5 ? 123 234 345 456 1234 2345 3456 12345 23456 123456 ?4 ? 10

? 其實仔細觀察這就是一個斐波拉切數列，0,1....n-2數的求和，動態規劃找到方程了就發現非常簡單了，這就是規律，但需要自己?去發現這個規律，有些題目咋看一臉懵逼，仔細看就會發現其中的規律。

?

學習地址：http://www.mamicode.com/info-detail-2634216.html

總結

以上是生活随笔為你收集整理的动态规划之等差递减区间个数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。