1 Arithmetic Slices
在等差數(shù)列的簡(jiǎn)單算法中，思路的重點(diǎn)就是對(duì)于符合等差的數(shù)列的擴(kuò)展的數(shù)字游戲
以[2 4 6 8 10]為例子
- 前三位
24 6為最短的等差數(shù)列 且只有dp =1
考慮8
2 4 6 8在上面等差數(shù)列擴(kuò)展了一位，那么這一位的增加她君，等差數(shù)列可選
2 4 6 8 對(duì) 2 4 6的位數(shù)延長(zhǎng)
4 6 8 增加的一個(gè)等差數(shù)列
所以為2
那么最后的等差數(shù)列就是 1+2=3逆害；
2.Arithmetic Slices II - Subsequence
但是在變形體中思杯，發(fā)現(xiàn)等差數(shù)列不僅下標(biāo)相差1太援，而且可以隨意從小到大去數(shù)字構(gòu)建等差數(shù)列德玫。
當(dāng)然還是動(dòng)態(tài)規(guī)劃問(wèn)題
但重點(diǎn)是怎么構(gòu)建動(dòng)態(tài)規(guī)劃的遞歸方程展哭。
考慮dp[i][diff]+=dp[j][diff]+1;
重點(diǎn)在于dp[i][diff]表示在0~i的所有數(shù)字中公差為diff的數(shù)字有多少個(gè)湃窍。
PS: diff=A[i]-A[j];
那么從圖像看一下
2
4 2->1
6 4->1 2->2（公差為4的數(shù)字一共2個(gè)）
8 6->1 4->1 2->3
10 8->1 6->1 4->2 2->4
然后所有的項(xiàng)-1然后求和
1+2+1+3=7
