300. 最长上升子序列
最长递增子序列的长度
暴力求解
略
动态规划
一个错解
定义:
- (dp[i])表示(nums[0:i])的LIS的长度;
状态转移:
- (dp[i])取决于(nums[i])是否大于(nums[0:i-1])的LIS中的最大值(这个最大值设为(m(i-1)));
[dp[0] = nums[0]
]
[egin{equation} dp[i]=left{ egin{aligned} dp[i-1] + 1 && if(nums[i]>m(i-1))\ dp[i-1] && otherwise end{aligned}
ight. end{equation}
]
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 0);
dp[0] = 1;
int m = nums[0];
for(int i = 1; i<n; ++i) {
if(nums[i]>m) {// 这里的评判标准m, 是数组nums[0:i]中的最大值, 而不是`nums[i]的所有LIS中的最大值`;
m = nums[i];
dp[i] = dp[i-1] + 1;
}else {
dp[i] = dp[i-1];
}
}
return dp[n-1];
}
};
正确实现
定义:
- (dp[i])表示(nums[0:i])的LIS的长度;
- 【注1】: 仅仅这样定义还不够, 实际上(dp[i])必须是(nums[0:i])的包含nums[i]的LIS的长度;
- 引用一下官方题解: "定义 (dp[i]) 为考虑前 (i) 个元素，以第 (i) 个数字结尾的最长上升子序列的长度，注意 nums[i] 必须被选取。"
初始状态:
- (dp[i])应初始化为1;
状态转移:
状态转移处在这样的情境: 已经计算出了(dp[0] sim dp[i-1]), 通过这些结果和(nums[i])获得(dp[i])的值;如何计算: (dp[i])取决于(nums[i])是否大于(nums[0:i-1])的LIS中的最大值- (nums[i])并不需要大于(nums[0:i-1])中的所有元素
- 在计算新的(dp[i] quad (i in [0,n-1])) 时, 遍历(dp[j] quad (j in [0, i-1]))
- Q: (dp[j])表示数组(nums[0:j])中含有的LIS的长度, 这个LIS未必包含(nums[j]), 为什么(nums[j] < nums[i])就可以产生(dp[i] = dp[j] + 1)的可能性? A: 是【注1】的定义, 为这样判断提供了可能性;
- 如果(nums[j] < nums[i]), 说明无论(nums[0: j])这个数组如何, 由于(dp[j])中保证存储的是包含nums[j]的LIS的长度(即(nums[j])是LIS中的最大值), 所以(dp[i] = dp[j] + 1)可以作为(dp[i])取值的一个选项;
- Q: 为什么要取max? A: 因为未修改之前的(dp[i])有可能大于(dp[j]+1); 这其实也是由【注1】的定义带来的;
- 如果(nums[j] le nums[i]), 说明包含(nums[j])的LIS对(dp[i])没有贡献, 后者保持;
转移方程:
[egin{equation} extrm{for each j} in [0, i-1] :quad dp[i]=left{ egin{aligned} max(dp[i], dp[j] + 1) && if(nums[j] < nums[i]) \ dp[i] && if(nums[j] ge nums[j]) end{aligned}
ight. quad end{equation}
]
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if(n==0) return 0;
vector<int> dp(n, 1);
for(int i = 1; i<n; ++i) {
for(int j = 0; j<i; ++j) {
if(nums[i]>nums[j]) {
dp[i] = max(dp[j] + 1, dp[i]);
}// else pass
}
}
return *max_element(dp.begin(), dp.end());
}
};
执行用时 :52 ms, 在所有 C++ 提交中击败了53.23%的用户
内存消耗 :9 MB, 在所有 C++ 提交中击败了5.07%的用户
注:
- 无后效性体现为, 当更改后面的(dp[i])时, 前面的(dp[j])不会被反馈地影响;