动态规划子序列问题系列一＞等差序列划分II

题目： 

 

---

解析： 

1.状态表示： 

 

---

2.状态转移方程： 

这里注意有个优化

 

---

3.初始化： 

 

---

4.填表顺序： 

 

---

5.返回值： 

返回dp表总和 

---

---

代码： 

public int numberOfArithmeticSlices(int[] nums) {int n = nums.length;int sum = 0;int[][] dp = new int[n][n];//初始化哈希表Map<Long,List<Integer>> hash = new HashMap<>();for(int i = 0; i < n; i++){long tmp = (long)nums[i];//判断一下哈希表中是否存在tmp这个元素,不存在就new List,再存放放入List数组中if(!hash.containsKey(tmp))hash.put(tmp,new ArrayList<>()); //哈希表存不存在tmp元素，都就放入List数组中hash.get(tmp).add(i);}for(int j = 2; j < n; j++)for(int i = 1; i < j; i++){long a = 2L * nums[i] - nums[j];//数据可能超出范围if(hash.containsKey(a))for(int x : hash.get(a))if(x < i)dp[i][j] += dp[x][i] + 1;else break; //小优化sum += dp[i][j];    }return sum;      }