LeetCode300. 最长递增子序列
题目链接：300. 最长递增子序列
独上高楼，望尽天涯路
感觉和之前的动态规划思路还不一样，没有想出好的递推公式。
慕然回首，灯火阑珊处
解决这道题的重点在于将dp数组设置为：dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度。
为什么一定表示 “以nums[i]结尾的最长递增子序” ，因为我们在 做 递增比较的时候，如果比较 nums[j] 和 nums[i] 的大小，那么两个递增子序列一定分别以nums[j]为结尾 和 nums[i]为结尾， 要不然这个比较就没有意义了，不是尾部元素的比较那么 如何算递增呢。
关于状态转移方程。
注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.size() == 1) return 1;
vector<int> dp(nums.size(), 1);
int result = 1;
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
if (result < dp[i]) {
result = dp[i];
}
}
return result;
}
};
LeetCode674. 最长连续递增子序列
题目链接：674. 最长连续递增子序列
独上高楼，望尽天涯路
和上一道题的解法异曲同工，只不过将dp[i]与dp[j]比较改成了dp[i]与dp[i-1]比较。
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
if (nums.size() == 1) return 1;
vector<int> dp(nums.size(), 1);
int result = 1;
for (int i = 1; i < nums.size(); i++) {
if (nums[i - 1] < nums[i]) {
dp[i] = dp[i - 1] + 1;
}
if (result < dp[i]) {
result = dp[i];
}
}
return result;
}
};
慕然回首，灯火阑珊处
思路一样。
LeetCode718. 最长重复子数组
题目链接：718. 最长重复子数组
独上高楼，望尽天涯路
对于二维dp数组的使用还不是很熟练。
慕然回首，灯火阑珊处
解题关键在于确定dp数组及下标的含义。
dp[i][j]：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。 （特别注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 ）
之所以dp[i][j]对应的是i-1和j-1，是为了方便初始化，如果对应的是i和j，则需要单独初始化dp[i][0]和dp[0][j]。
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
int result = 0;
for (int i = 1; i <= nums1.size(); i++) {
for (int j = 1; j <= nums2.size(); j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
if (result < dp[i][j]) {
result = dp[i][j];
}
}
}
return result;
}
};