动态规划34：446. 等差数列划分 II - 子序列

动态规划解题步骤：

1.确定状态表示：dp[i]是什么

2.确定状态转移方程：dp[i]等于什么

3.初始化：确保状态转移方程不越界

4.确定填表顺序：根据状态转移方程即可确定填表顺序

5.确定返回值

题目链接：446. 等差数列划分 II - 子序列 - 力扣（LeetCode）

题解1（三层for循环）：

1.状态表示：dp[i][j]表示以nums[i] nums[j]结尾的等差子序列个数

2.状态转移方程：dif=nums[j]-nums[i]

                            如果存在nums[k]=nums[i]-dif  0<=k<i  （可能存在多个nums[k]，每个都要算）

                            dp[i][j]+=dp[k][i]+1

3.初始化：创建dp表时全部初始化为0

4.填表顺序：从上往下，从左往右哦，依次填写二维dp表

5.返回值：返回dp表中所有元素之和（理论上是上三角部分，但是由于下三角和对角线都为0，因此返回总和也没问题）

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {//dp[i][j]表示以nums[i] nums[j]结尾的等差子序列个数//dif=nums[j]-nums[i]//nums[k]=nums[i]-dif//如果存在nums[k] 0<=k<i//重复的nums[k]也算//dp[i][j]+=dp[k][i]+1size_t n=nums.size();//创建dp表vector<vector<int>> dp(n,vector<int>(n,0));//初始化//创建dp表时全部初始化为0//填表for(int j=2;j<n;++j){for(int i=1;i<j;++i){long long dif=(long long)nums[j]-nums[i];long long temp=nums[i]-dif;for(int k=0;k<i;++k){if(nums[k]==temp){   dp[i][j]+=dp[k][i]+1;}}}}//返回值：返回dp表之和，2处理为0int ans=0;for(auto row:dp){for(auto value:row){ans+=value;}}return ans;}};

题解2（使用hash表代替一层for循环）：

在填dp表之前，先将所有nums值和其对应的下标填入hash表，对于重复的nums值存在多个下标，使用vector存储其下标。查找nums[k]时使用hash表查找，hash[nums[k]]返回存储下标的vector，再遍历一次vector得到所有的k，但是只有满足小于i的k才符合条件。

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {//dp[i][j]表示以nums[i] nums[j]结尾的等差子序列个数//dif=nums[j]-nums[i]//nums[k]=nums[i]-dif//如果存在nums[k] 0<=k<i//重复的nums[k]也算//dp[i][j]+=dp[k][i]+1size_t n=nums.size();//创建hash表：nums值和下标绑定//重复元素有多个下标，则使用数组存储unordered_map<long long,vector<int>> hash;for(int i=0;i<n;++i){hash[nums[i]].push_back(i);}//创建dp表vector<vector<int>> dp(n,vector<int>(n,0));//初始化//创建dp表时全部初始化为0//填表for(int j=2;j<n;++j){for(int i=1;i<j;++i){long long dif=(long long)nums[j]-nums[i];long long temp=nums[i]-dif;if(hash.count(temp)){for(auto k:hash[temp]){if(k<i)dp[i][j]+=dp[k][i]+1;}}}}//返回值：返回dp表之和，2处理为0int ans=0;for(auto row:dp){for(auto value:row){ans+=value;}}return ans;}};