LeetCode 1027. 最长等差数列（二维动态规划）

2020年9月23日 周三 天气晴 【不悲叹过去，不荒废现在，不惧怕未来】

二维DP

因为一个数能够跟任何数成等差，即diff的个数理论上是无限的，但题目限定了元素大小，0 <= A[i] <= 10000，那么等差值范围为 [-10000,10000]。

用二维数组dp[i][diff]表示以i处元素结尾，公差为diff的子序列长度。因为数组索引不能为负值，因此设置一个偏移量offse=10000，将[-10000,10000]映射到[0,20000]。

class Solution {
    public:int longestArithSeqLength(vector<int>& A) {
    int n = A.size();if(n<2) return n;int offset = 10000;vector<vector<int>> dp(n,vector<int>(20001,1));int maxLen = 1;for(int i=1;i<n;++i){
    for(int j=0;j<i;++j){
    // 求公差diffint diff = A[i] - A[j] + offset;// dp[i][diff]表示以i处元素结尾，公差为diff的子序列长度dp[i][diff] = dp[j][diff] + 1;maxLen = max(maxLen,dp[i][diff]);}}return maxLen;}
};

• 时间复杂度：$O\left(n^2\right)$
• 空间复杂度：$O\left(n^2\right)$

参考文献

https://leetcode-cn.com/problems/longest-arithmetic-subsequence/solution/dong-tai-gui-hua-by-wushaoling-4/