[C++知识库]【每日一题】LeetCode300. 最长递增子序列【线性DP】

思路

典型DP
状态：dp[i]表示以i结尾的最长上升子序列的长度。
状态转移方程: $dp[i]=max(dp[i],dp[j]+1),j<i$

AC代码

C++

class Solution {
public:
    // dp[i] 表示以i结尾的最长上升子序列的长度
    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        int dp[len];
        int ans = 0;
        for(int i = 0; i < len; ++i) dp[i] = 1;
        for(int i = 1; i < len; ++i){
            for(int j = 0; j < i; ++j){
                if(nums[j] < nums[i]){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
        }
        for(int i = 0; i < len; ++i) ans = max(ans,dp[i]);
        return ans;
    }
};

Python

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        length = len(nums)
        dp = [1]*length
        for i in range(1,length):
            for j in range(0,i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i],dp[j]+1)
        return max(dp)