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

标题： 
  

 
  

---

  解析： 
  1.状态表现： 
  

 
  

---

  2.状态转移方程： 
  这里注意有个优化
  

 
  

---

  3.初始化： 
  

 
  

---

  4.填表顺序： 
  

 
  

---

  5.返回值： 
  返回dp表总和 
  

---

  

---

  代码： 

1. public int numberOfArithmeticSlices(int[] nums) {
2.         int n = nums.length;
3.         int sum = 0;
4.         int[][] dp = new int[n][n];
6.         //初始化哈希表
7.         Map<Long,List<Integer>> hash = new HashMap<>();
8.         for(int i = 0; i < n; i++){
9.             long tmp = (long)nums[i];
10.             //判断一下哈希表中是否存在tmp这个元素,不存在就new List,再存放放入List数组中
11.             if(!hash.containsKey(tmp))
12.               hash.put(tmp,new ArrayList<>());
14.             //哈希表存不存在tmp元素，都就放入List数组中
15.             hash.get(tmp).add(i);
16.         }
18.         for(int j = 2; j < n; j++)
19.             for(int i = 1; i < j; i++){
20.                 long a = 2L * nums[i] - nums[j];//数据可能超出范围
21.                 if(hash.containsKey(a))
22.                     for(int x : hash.get(a))
23.                         if(x < i)
24.                           dp[i][j] += dp[x][i] + 1;
25.                         else break; //小优化
26.                 sum += dp[i][j];   
27.             }
29.         return sum;      
30.     }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。