LeetCode.300.673(动态规划)

代码随想录就是我爹，没他这两题这个月都不能AC

今天两题全靠评论区AC，下次一定要雪耻

300.最长递增子序列

class Solution {
  public:
    int lengthOfLIS(vector<int> &nums) {
        if (nums.size() <= 1)
            return nums.size();
        vector<int> dp(nums.size(), 1);
        int result = 0;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            result = max(dp[i], result);
        }
        return result;
    }
    // 54/54 cases passed (264 ms)
    // Your runtime beats 50.02 % of cpp submissions
    // Your memory usage beats 78.44 % of cpp submissions (10.2 MB)
    //*我他妈怎么连这个都没想到。。。
    // TODO:雪耻再做
};

673.最长递增子序列的个数

class Solution {
  public:
    int findNumberOfLIS(vector<int> &nums) {
        if (nums.size() <= 1)
            return nums.size();
        vector<int> dp(nums.size(), 1);
        vector<int> count(nums.size(), 1);
        int maxCount = 0;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j]; //找到并行的可能
                    }
                }
                if (dp[i] > maxCount)
                    maxCount = dp[i];
            }
        }
        int result = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (maxCount == dp[i])
                result += count[i];
        }
        return result;
        // 223/223 cases passed (152 ms)
        // Your runtime beats 16.8 % of cpp submissions
        // Your memory usage beats 74.5 % of cpp submissions (12.8 MB)
        //同时维护两个数组，而且最后的结果并不是在数组的开头或是结尾打印的，大可不比一定要追求这一点
        // TODO:雪耻再做
    }
};