跳轉(zhuǎn)匯總鏈接

👉🔗算法題匯總鏈接

1.2 等差數(shù)列劃分

🔗題目鏈接

如果一個數(shù)列 至少有三個元素 ，并且任意兩個相鄰元素之差相同，則稱該數(shù)列為等差數(shù)列。例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差數(shù)列。
給你一個整數(shù)數(shù)組 nums ，返回數(shù)組 nums 中所有為等差數(shù)組的子數(shù)組個數(shù)。 子數(shù)組是數(shù)組中的一個連續(xù)序列。

1. 狀態(tài)表示：
   • dp[i] 表示以 i 位置為結(jié)尾的等差數(shù)列的子數(shù)組個數(shù)。
2. 狀態(tài)轉(zhuǎn)移方程：
   • 等差數(shù)列只需要判斷三個數(shù)字就能確定，我們設(shè) i-2、i-1 和 i 位置為 a、b、c，當(dāng) c 的加入能形成等差數(shù)列時，dp[i] 位置的數(shù)（等差子數(shù)組個數(shù)）需要加上 abc 這個子數(shù)組，也就是在 dp[i-1] 的基礎(chǔ)上加一即可。得到狀態(tài)轉(zhuǎn)移方程如下，

   dp[i] = if(c-b == b-a), dp[i-1]+1 if(c-b != b-a), 0
   

3. 初始化
   • 把頭兩位置零，vector 的初始化就是 0，所以可以不用管。
4. 填表順序
   • 從左往右。
5. 返回值
   • dp 表內(nèi)所有值的和。

🐎代碼如下：

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {size_t n = nums.size();vector<int> dp(n);size_t sum = 0;for(size_t i = 2; i < n; i++){dp[i] = nums[i]-nums[i-1] == nums[i-1]-nums[i-2] ? dp[i-1] + 1 : 0;sum += dp[i];}return sum;}
};

🥰如果本文對你有些幫助，歡迎👉 點贊 收藏 關(guān)注，你的支持是對作者大大莫大的鼓勵！！(????) 若有差錯懇請留言指正~~