c++ - 进一步优化 DP 解决方案的提示

问题描述

我解决了 LeetCode 上的最长增加子序列问题：https ://leetcode.com/problems/longest-increasing-subsequence/

给定一个未排序的整数数组，求最长递增子序列的长度。对于[10,9,2,5,3,7,101,18]，答案是4（的大小[2,3,7,101]）。

class Solution {
public:
    int helper(vector<int>& nums, unordered_map<int, vector<int>>& dp, int lastNum, int startIndex) {
        if(startIndex>=nums.size()) return 0;
        if(dp.find(lastNum)!=dp.end() && dp[lastNum].size()>=startIndex && dp[lastNum][startIndex]!=INT_MIN) {
            return dp[lastNum][startIndex];
        }
        
        int ans=0;
        if(nums[startIndex]>lastNum) ans=1+helper(nums, dp, nums[startIndex], startIndex+1);
        ans=max(ans, helper(nums, dp, lastNum, startIndex+1));
        
        return dp[lastNum][startIndex]=ans;
    }
    
    int lengthOfLIS(vector<int>& nums) {
        int ans=0;
        unordered_map<int, vector<int>> dp;
        dp[INT_MIN].resize(10001, INT_MIN);
        for(int i=0; i<nums.size(); i++) dp[nums[i]].resize(10001, INT_MIN);
        
        return helper(nums, dp, INT_MIN, 0);
    }
};

请注意，我也在记忆它，使用上dp表并使用两个状态lastNum（nums[i]我们在上次递归中选择的值）和startIndex. 在解决方案部分，他们使用两种状态prev（index，与我传递的值lastNum不同）和curpos（类似于startIndex）。

我很困惑，因为我仍然得到 TLE。现在我知道在线评委设置的时间限制是任意的，但我想看看为什么使用lastNum而不是prev作为状态会导致更多的执行时间。同样，我还可以进行其他优化吗？

谢谢！

编辑：10001根据 Igor 在评论中的建议，我将其更改为，现在所有测试用例都通过了，但这需要很长时间：

24 / 24 个测试用例通过，但耗时太长。

Edit2：换一种说法，我想我的问题是，作为一名面试官，人们会提供什么建议来推动候选人朝着正确的方向前进（prev而不是使用lastNum）？

标签： c++algorithmoptimizationdynamic-programming

不确定您的解决方案，但我在这里有点困惑：dp[INT_MIN].resize(10000001, INT_MIN);，也许您的解决方案不是 O(N)。这会被接受：

#include <vector>
#include <algorithm>

struct Solution {
    static const inline int lengthOfLIS(const std::vector<int> &nums) {
        std::vector<int> longest;

        for (unsigned int index = 0; index < nums.size(); index++) {
            const auto iter = std::lower_bound(longest.begin(), longest.end(), nums[index]);

            if (iter == longest.end()) {
                longest.emplace_back(nums[index]);

            } else {
                *iter = nums[index];
            }
        }

        return longest.size();
    }
};

参考

有关其他详细信息，您可以查看讨论板。有很多公认的解决方案，其中包含多种语言和解释、高效算法以及渐近时间/空间复杂度分析^1、2。

如果你正在准备面试：

我们希望根据标准和约定（例如c ¹^,² , c++ ¹^,² , java ¹^,² , c# ¹^,² , python ¹ , javascript ¹ , go ¹ , rust ¹ ）编写无错误和干净的代码）。

c++ - 进一步优化 DP 解决方案的提示

问题描述

解决方案

参考

如果你正在准备面试：

推荐阅读