阶段不足以表示可推导的状态：附加信息作为状态维度

摘要: 找到阶段划分后，有时发现需要增加附加信息才能得到可以推导的状态表示

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

对于一个动态规划的问题。最重要的是找到状态表示和阶段划分，其中阶段划分相对比较简单，因为往往具有物理意义，比如时间、距离、步数、子图的顶点集合等。

但是很多时候发现状态表示中必须要增加附加信息，才能使得状态表示对应的子问题具有最优子结构。进而得到动态规划的状态表示，使得可以由此前阶段的状态(对应的子问题)的答案推导出当前阶段的状态。

附加的状态信息有可能会很稀疏，也就是说分布会很散，有的值很大，有的值很小，可能还有负数，这一维附加状态可以用哈希表来维护其取值。

本文我们以 446. 等差数列划分 II - 子序列 为例来看一下这种阶段不足以表示状态的情况怎么处理。

---

等差子序列个数问题

446. 等差数列划分 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] 的一个子序列。

题目数据保证答案是一个 32-bit 整数。

提示：

1  <= nums.length <= 1000
-2^31 <= nums[i] <= 2^31 - 1

示例 1：
输入：nums = [2,4,6,8,10]
输出：7
解释：所有的等差子序列为：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

示例 2：
输入：nums = [7,7,7,7,7]
输出：16
解释：数组中的任意子序列都是等差子序列。

---

算法：动态规划

阶段划分

这是一个单串的场景，仿照 LIS 的阶段划分方式，定义 $dp[i]$ 表示考虑前 $i$ 个元素，以 $nums[i]$ 结尾的等差子序列个数。阶段划分是已经处理的前缀长度 $i$。

在 LIS 问题中，仅用阶段 $i$ 表示状态，其代表的子问题已经具有最优子结构了，也就是：先前阶段已经算出的 $dp[j], 0\leq j < i$ 中，通过满足 $a[j] < a[i]$ 的这部分 $dp[j]$ 就可以得到当前状态的结果 $dp[i]$。

附加信息

但是这里并不成立。假设我们在先前阶段已经算出 $dp[j], 0 \leq j < i$，如果 $dp[j]$ 对 $dp[i]$ 有贡献，那么统计的就是公差 $d_{j} = a[i] - a[j]$ 的子序列个数。但是能以 $a[i]$ 结尾的等差子序列可能不止公差为 $d_{j}$ 这一种。

但如果限制公差为 $k$，将状态定义为 $dp[i][k]$ 表示虑前 $i$ 个元素，以 $nums[i]$ 结尾，公差为 $k$ 的等差子序列个数，这就存在最优子结构了：只需要先前阶段已经求出的 $dp[j][k], 0\leq j < i$ 中，满足 $a_{i} - a_{j} = k$ 的这部分 $dp[j][k]$ 即可计算出 $dp[i][k]$。

状态转移方程

状态定义为 $dp[i][k]$ 表示考虑前 $j$ 个元素，以 $j$ 结尾，公差为 $k$ 的等差子序列个数。已经处理的前缀长度为阶段，$d$ 作为附加信息，为需要的公差。

状态转移方程如下：

$$dp[i][a[i] - a[j]] = \sum\limits_{0\leq j < i}(dp[j][a[i] - a[j]] + 1)$$

在转移的时候，状态总是从一个阶段转移到另一个阶段，因此没必要关心附加信息维度的大小变化情况，也就是附加状态维度的推导方向不重要，无后效性已经由阶段保证。也就是在同样的 $i$ 下，$j$ 从 $0$ 到 $i$ 的顺序不重要。

稀疏维度处理

由于公差比较稀疏，也就是说分布会很散，有的公差很大，有的公差很小，可能还有负数，这一维附加状态可以用哈希表来维护其取值。

代码 (C++)

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int n = A.size();
        using ll = long long;
        // dp[i][d] := 以 i 结尾的公差为 k 子序列
        vector<unordered_map<ll, int>> dp(n, unordered_map<ll, int>()); 
        int ans = 0;
        for(int i = 1; i < n; ++i)
        {
            // dp[i][d]
            for(int j = 0; j < i; ++j)
            {
                ll d = (ll)A[i] - A[j];
                int sum = 0;
                if(dp[j].find(d) != dp[j].end())
                    sum = dp[j][d];
                dp[i][d] += sum + 1;
                // 上面 1 的部分是长度为 2 的，转移时有用但不统计进结果
                ans += sum; 
            }
        }
        return ans;
    }
};

---