回文串与回文子序列问题（动态规划）
写在前面
今天瞟了一眼每日一题，发现是中等题目，于是我就打算解一下，结果我连题目都没读懂。
题目是516.最长回文子序列。
这道题目用到的解题技巧多数是动态规划。然鹅我并不懂什么是动态规划，好在下学期的《算法设计》里面会讲到。趁着如今还是暑假，我决定先把这块硬骨头啃掉，但是咱并不能一口吃个胖子，所以要循序渐进的一步一步来。
最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
1
2
3
| 输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
|
示例 2：
1
2
| 输入：nums = [0,1,0,3,2,3]
输出：4
|
示例 3：
1
2
| 输入：nums = [7,7,7,7,7,7,7]
输出：1
|
提示：
1 <= nums.length <= 2500-104 <= nums[i] <= 104
思路
dp[i]表示i之前包括i的最长上升子序列。
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
这一步要理解，目的就是为了更新dp[i]，每遍历一次对应位置的dp[i]都要被更新或不更新。dp[j]代表直到j这个位置的数字的最长子序列有多长，因为nums[i]>nums[j]了，所以i这个位置的数字的最长子序列的长度肯定比j这个位置长，那么就dp[j]+1，然后再与目前dp[i]比一下大小，如果大就更新，如果小于或等于就不更新。这样可以确保，一次遍历后，dp[i]的值就是到i这个位置的最长子序列的长度。
每一个i，对应的dp[i]（即最长上升子序列）起始大小至少都是是1.
dp[i] 是由0到i-1各个位置的最长升序子序列 推导而来，那么遍历i一定是从前向后遍历。
j其实就是0到i-1，遍历i的循环里外层，遍历j则在内层，代码如下：
1
2
3
4
5
6
| 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);
}
if (dp[i] > res) res = dp[i];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.size()<2)
return nums.size();
vector<int> dp(nums.size(), 1);
int res = 1;
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);
}
if(dp[i]>res)
res = dp[i];
}
return res;
}
};
|
最长连续递增序列
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标l和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1：
1
2
3
4
| 输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
|
示例 2：
1
2
3
| 输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。
|
提示：
1 <= nums.length <= 104
109 <= nums[i] <= 109
思路
上面求最长升序子序列，并未要求连续。所以最长递增子序列，存在离散情况，需要使用j与i依次进行比较。但本题要求连续 ，所以不必使用j，即不必使用双重循环。一次for循环就好。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
if (nums.size()==0)
return 0;
int res = 1;
vector<int> dp(nums.size() ,1);
for(int i = 0;i<nums.size()-1;i++)
{
if(nums[i+1]>nums[i])
dp[i+1] = dp[i]+1;
if(res<dp[i+1])
res = dp[i+1];
}
return res;
}
};
|
上面使用了dp数组，实际上不必另创数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int sum = 1;
int count = 1;
for(int i = 0;i<nums.size()-1;i++){
if(nums[i]<nums[i+1])
{
count++;
sum = max(sum,count);
}else{
count = 1;
}
}
return sum;
}
};
|
在写这道题目的时候，突然啊想起来了训练2的买卖股票的最佳时机 II,于是就想着能不能用动态规划把那道题解一下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
vector<vector<int>> dp(len, vector<int>(2, 0));
dp[0][0] -= prices[0];
dp[0][1] = 0;
for (int i = 1; i < len; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
return dp[len - 1][1];
}
};
|
