[数据结构与算法]leetcode动态规划day2

今天事情多又是开会又是讨论的，只做了一道最长递增子序列，leetcode300

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());
    }
};

vector可以用fill对容器进行填满，在动态规划里我感觉今天这个题算简单点的，有点一维的意思，只需要在第二层遍历的过程中比有没有比当前大的并存入dp中就行，dp初始值是1因为自己都是自己的最长公共子序列。状态转移方程是：

dp[i] = max(dp[i], dp[j] + 1)

因为我们在第二次遍历中可能发现的不是最长的，所以需要比较取较大值。

最后返回的：

return *max_element(dp.begin(), dp.end());

也学到了，max_element，自己是迭代器？