动态规划

最长递增子序列问题（Longest Increasing Subsequence）

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

这是我写的代码（有点差劲的代码

class Solution {
public:
    vector<int> dp;
    int tryThrough(vector<int>& nums) {
        int res = 0x80000000;
        for (int i = 0; i < nums.size(); i++) {
            if(dp[i] > res){
                res = dp[i];
            }
        }
        return res;
    }
    int lengthOfLIS(vector<int>& nums) {
        dp.push_back(1);
        for (int i = 1; i < nums.size(); i++) {
            dp.push_back(1);
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && dp[j] >= dp[i])
                    dp[i] = dp[j] + 1;
            }
        }
        for (auto& tmp : dp) {
            std::cout << tmp << ' ';
        }
        return tryThrough(nums);
    }
};

写的过程中出现了一下几个问题

tryThrough 函数中把 dp[i] 写成 nums[i]，遗忘了需要遍历的是子序列的长度
lengthOfLIS 中一开始习惯性的认为需要前两个元素 dp[0] 和 dp[1]，而且想当然的认为 dp[1] 等一 1，实际上我一边认为 dp[0] 应该是某种虚的最长子序列，另一边我认为 dp[i] 表示长度 i+1 的以 nums[i] 结尾的最长子序列。
在处理 dp[j] >= dp[i] 时，写成了 dp[j] > dp[i]，想当然的认为大于才能递增，实际上可能存在相等的情况，这里正确的逻辑应该是 max(dp[i],dp[j]+1)

再来看一下优秀代码，leetcode 官网的优雅代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = (int)nums.size();
        if (n == 0) {
            return 0;
        }
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};