算法笔记之动态规划——等差数列划分 II - 子序列

利用动态规划处理序列问题，很经典的题目，记录一下。

题目描述

LeetCode446. 等差数列划分 II - 子序列

给你一个整数数组 nums ，返回 nums 中所有 等差子序列 的数目。

如果一个序列中 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该序列为等差序列。

• 例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。
• 再例如，[1, 1, 2, 5, 7] 不是等差序列。

数组中的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。

例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。

思路分析

首先我们新增一个定义，把只有2个元素的序列称为弱等差序列，弱等差序列虽然不是等差序列，当时它只要增加元素就会变成等差序列。

这样我们可以二重遍历元素，针对每个元素，求它和之前元素的弱等差序列并进行记录，如果前面已经存在相同差的弱等差序列，则添加一个元素后，一定是等差序列，我们就可以对结果加1。

当前元素每个弱等差序列元素数量等于已有的元素（也许之前存在多个相同元素）加上前一个元素的相同弱等差序列的元素数量再加上1（前一个元素和本元素组成的弱等差序列）。

Java代码

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        if(nums.length <= 2) {
            return 0;
        }
        // 哈希表记录每个元素的弱等差数列
        // 键是相邻元素之差，值是序列中元素数量
        Map<Long, Integer>[] dp = new Map[nums.length];       
        for(int i = 0; i < dp.length; i++) {
            dp[i] = new HashMap<Long, Integer>();
        }

        int r = 0;
        // 二重循环遍历
        for(int i = 1; i < nums.length; i++) {
            for(int j = 0; j < i; j++) {
                Long d = (long)nums[i] - nums[j];
                int c = dp[j].getOrDefault(d, 0);
                r += c;
                int c2 = dp[i].getOrDefault(d, 0);
                // 注意这里还要加一个弱等差数列
                dp[i].put(d, c2 + c + 1);
            }
        }
        return r;
    }
}