动态规划32：873. 最长的斐波那契子序列的长度

动态规划解题步骤：

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

2.确定状态转移方程：dp[i]等于什么

3.初始化：确保状态转移方程不越界

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

5.确定返回值

题目链接：873. 最长的斐波那契子序列的长度 - 力扣（LeetCode）

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

1.状态表示：dp[i][j]表示以arr[i]和arr[j]作为最后两个元素的最长的斐波那契子序列的长度

2.状态转移方程：如果存在arr[k]=arr[j]-arr[i] 0=<k<i，dp[i][j]=dp[k][i]+1

                            如果不存在，dp[i][j]=2（实际值为0，最后返回值时会将值2的返回值处理为0）

3.初始化：如果构成斐波那契数列则长度至少为3，无法构成斐波那契数列长度为0，但是为了便于状态转移方程的计算，将无法构成斐波那契数列的dp值设为2

4.填表顺序：二维dp表，从上往下，从左往右依次遍历填写

5.返回值：返回dp表中的最大值，另外需要将返回值为2的值处理为0

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        //dp[i][j]表示以arr[i]和arr[j]作为最后两个元素的最长的斐波那契子序列的长度
        //如果存在arr[k]=arr[j]-arr[i] 0=<k<i
        //dp[i][j]=dp[k][i]+1
        //如果不存在
        //dp[i][j]=2（暂时设为2，便于动态规划计算，实际值应该为0）

        size_t n=arr.size();
        //创建dp表
        vector<vector<int>> dp(n,vector<int>(n,2));
        //初始化
        //全部初始化为2，但实际值为0
        //填表
        for(int j=2;j<n;++j)
        {
            for(int i=0;i<j;++i)
            {                            
                int dif=arr[j]-arr[i];
                for(int k=0;k<i;++k)
                {
                    if(arr[k]==dif)
                    {
                        dp[i][j]=dp[k][i]+1;
                    }   
                }
            }
        }
        //返回值
        int ans=0;
        for(auto row:dp)
            for(auto value:row)
                if(value>ans) ans=value;
        return ans==2?0:ans;
    }
};

题解2（两层for循环，使用Hash表替代一层循环）：

题解1有三层for循环，时间复杂度为O(n^3)，为了降低时间复杂度，将arr[k]的查找由原本的for循环遍历查找改为使用Hash表查找，Hash表查找的时间复杂度为O(n)

建立Hash表，将arr中的元素和其下标绑定，由于题目给的是严格递增的序列，所以无需考虑Hash表对于重复元素的查找。

此外，由于hash表查找使用[ ]的方式，如果查找不到会自动构建int并返回0，该情况和查找到arr[k]的位置是第一个元素冲突，所以需要先使用count判断是否存在arr[k]。同时要注意，查找到的arr[k]的k下标必须是大于等于 0 且小于 i 的。

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        //dp[i][j]表示以arr[i]和arr[j]作为最后两个元素的最长的斐波那契子序列的长度
        //如果存在arr[k]=arr[j]-arr[i] 0=<k<i
        //dp[i][j]=dp[k][i]+1
        //如果不存在
        //dp[i][j]=2（暂时设为2，便于动态规划计算，实际值应该为0）

        size_t n=arr.size();
        //优化：建立hash表，将arr[i]和下标绑定
        //这样就可以不用遍历查找arr[k]，直接通过hash表查找arr[k]，随后返回其下标
        unordered_map<int,int> hash;
        for(int i=0;i<n;++i) hash[arr[i]]=i;
        //创建dp表
        vector<vector<int>> dp(n,vector<int>(n,2));
        //初始化
        //全部初始化为2，但实际值为0
        //填表
        for(int j=2;j<n;++j)
        {
            for(int i=0;i<j;++i)
            {                            
                int dif=arr[j]-arr[i];
                if(hash.count(dif))
                {
                    int k=hash[dif];
                    if(k>=0&&k<i) dp[i][j]=dp[k][i]+1;
                }
                // for(int k=0;k<i;++k)
                // {
                //     if(arr[k]==dif)
                //     {
                //         dp[i][j]=dp[k][i]+1;
                //     }   
                // }
            }
        }
        //返回值
        int ans=0;
        for(auto row:dp)
            for(auto value:row)
                if(value>ans) ans=value;
        return ans==2?0:ans;
    }
};

原文地址：https://blog.csdn.net/2301_76197086/article/details/143831397

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！