动态规划31：1218. 最长定差子序列

解题步骤：

1.确定状态表示：dp[i]是什么

2.确定：dp[i]等于什么

3.：确保不越界

4.确定填表顺序：根据状态转移方程即可确定填表顺序

5.确定返回值

题目链接：

题解1（两层for循环超时）：

1.状态表示： dp[i]表示以arr[i]结尾的最长定差子序列长度

2.状态表示：如果存在arr[j]+difference=arr[i] dp[i]=max(dp[i],dp[j]+1) 0=<j<i

3.初始化：dp表最低值为1，所以创建dp表时全部初始化为1

4.填表顺序：从左向右，依次填写

5.返回值：返回dp表中的最大值

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        //dp[i]表示以arr[i]结尾的最长定差子序列长度
        //如果存在arr[j]+difference=arr[i] dp[i]=max(dp[i],dp[j]+1) 0=<j<i
        //如果不存在 dp[i]=1

        size_t n=arr.size();
        //创建dp表
        vector<int> dp(n,1);
        //初始化：全部初始化为1
        //填表
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<i;++j)
            {
                if(arr[j]+difference==arr[i])
                    dp[i]=max(dp[i],dp[j]+1);
            }
        }
        //返回值
        int ans=0;
        for(auto e:dp) if(e>ans) ans=e;
        return ans;
    }
};

题解2（hash表中动态规划，一次循环）：

1.状态表示：创建hash表unordered_map<int,int> first表示arr[i]，second表示dp[i]

2.状态转移方程：遍历数组arr，如果要构成等差子序列，则必须存在arr[i]-difference，即hash[arr[i]-difference]一定存在。如果不存在，hash[arr[i]-difference]默认为0，+1正好初始化为1。

同时由于是从左向右遍历数组arr，所以对于arr中的相同元素来说，最后一次填写到hash表中的一定是最右侧元素。

故状态转移方程：hash[arr[i]]=hash[arr[i]-difference]+1

3.初始化：填表时初始化

4.填表顺序：从左向右，依次填写

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        //dp[i]表示以arr[i]结尾的最长定差子序列长度
        //如果存在arr[j]+difference=arr[i] dp[i]=max(dp[i],dp[j]+1) 0=<j<i
        //如果不存在 dp[i]=1

        //优化：
        //相同元素的dp值，一定是最右侧的元素dp值大
        //所以无需遍历arr[i]前面的元素，建立哈希表将arr[i]和dp值绑定
        //从左向右一次遍历，对于相同的元素，最终得到的一定是最右侧元素的dp值

        size_t n=arr.size();
        //创建hash表
        unordered_map<int,int> hash;//arr[i]-dp[i]
        //填表
        for(int i=0;i<n;++i)
        {
            //如果不存在arr[j]+difference=arr[i]，即hash[arr[i]-difference]不存在
            //自动构建并将second（即dp）初始化为0
            hash[arr[i]]=hash[arr[i]-difference]+1;
        }
        //返回值
        int ans=0;
        for(auto& e:hash) if(e.second>ans) ans=e.second;
        return ans;
    }
};