algo-aha

等差子段的个数

• https://leetcode.com/problems/arithmetic-slices/

int numberOfArithmeticSlices(vector<int>& A) {
    // 设dp[i]表示以A[i]结尾的等差子段数。
    // 若A[i]-A[i-1]=A[i-1]-A[i-2]时，dp[i]=dp[i-1]+1；
    // 其中dp[i-1]来自扩展的旧子段，1来自新出现的长度==3的子段。
    // 若不满足等差，dp[i]=0。
    // 初始dp[0]=dp[1]=0，因为长度要>=3。
    // i这维只依赖前一项，省掉i这维，满足等差时dp+=1，不满足时dp=0。
    int dp = 0, ans = 0;
    for (int i = 2; i < A.size(); i++) {
        if (A[i] - A[i-1] == A[i-1] - A[i-2]) {
            dp += 1;
            ans += dp;
        } else {
            dp = 0;
      }
    }
    return ans;
}

等差子序列的个数

• https://leetcode.com/problems/arithmetic-slices-ii-subsequence/

设dp[i]表示以A[i]结尾的等差子序列个数，递推过程太复杂，说明假设缺少信息。

int numberOfArithmeticSlices(vector<int>& A) {
    // 设dp[i][d]表示以A[i]结尾、等差为d、长度>=2的等差子序列数。
    // 对所有j<i，d=A[i]-A[j]，dp[i][d]=sum(dp[j][d]+1)
    // 其中dp[j][d]来自扩展的旧序列，1来自新出现的长度==2序列
    // 优化：由于d是两数之差，范围无限，dp[i][d]的d这一维要用unordered_map
    // 要用dp[j].count(d)测试，防止d值不存在时往map里添0，导致内存溢出
    const int N = A.size();
    vector<unordered_map<int,int>> dp(N);
    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < i; j++) {
            long d = (long)A[i] - A[j];
            if (d < INT_MIN || d > INT_MAX) continue; // pass OL
            int dp_jd = dp[j].count(d) ? dp[j][d] : 0;
            dp[i][d] += dp_jd + 1;
            // dp[j][d]是扩展的旧序列，现在长度>=3，统计长度>=3的
            ans += dp_jd;
        }
    }
    return ans;
}

最长等差子序列

• https://leetcode.com/problems/longest-arithmetic-sequence/

int longestArithSeqLength(vector<int>& A) {
    // 最长等差子序列长
    // 设dp[i][d]表示以A[i]结尾、等差为d的子问题解
    const int N = A.size();
    vector<unordered_map<int,int>> dp(N);
    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < i; j++) {
            int d = A[i] - A[j];
            dp[i][d] = dp[j].count(d) ? (dp[j][d] + 1) : 2;
            ans = max(ans, dp[i][d]);
        }
    }
    return ans;
}

指定等差的最长子序列

• https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/

int longestSubsequence(vector<int>& arr, int difference) {
    // 最长指定差的子序列长
    // ~~O(n^2)解法超时：设dp[i]表示以A[i]结尾、等差为difference的子问题解~~
    // 设dp[v]表示子序列结尾值为v的子问题解，dp[v] = dp[v-difference]+1
    unordered_map<int, int> dp; // 子序列结尾值v=>子序列长
    int ans = 0;
    for (int v : arr) {
        dp[v] = dp.count(v - difference) ? dp[v - difference] + 1 : 1;
        ans = max(ans, dp[v]);
    }
    return ans;
}

最长Fib子序列

• https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/

int lenLongestFibSubseq(vector<int>& A) {
    // 设dp[i][j]表示以A[i]、A[j]结尾的长>=2的最长Fib子序列长
    // 将A中值作val=>idx的映射，i,j的前一个索引idx=mp[A[j]-A[i]]，
    // dp[i][j] = dp[idx][i] + 1
    // i从左往右遍历，j从左往右遍历
    const int N = A.size();
    unordered_map<int, int> mp; // val=>idx
    vector<vector<int>> dp(N, vector<int>(N, 0));

    int ans = 0;
    for (int j = 0; j < N; j++) {
        mp[A[j]] = j;
        for (int i = 0; i < j; i++) {
            int val = A[j] - A[i];
            if (val < A[i] && mp.count(val)) {
                int idx = mp[val];
                dp[i][j] = dp[idx][i] + 1; // dp[i][j]现在>=3
                ans = max(ans, dp[i][j]);                        
            } else {
                dp[i][j] = 2;
            }                
        }
    }
    return ans;
}