第一题:
简介:
动态规划五部曲:
1.确定 dp数组下标的定义
dp[i] 到达 i 时 最长递增子序列的长度
2.确定递推公式
我们确定当前的最大长度需要遍历前面所有的最大长度,然后如果序列最后一个值小于nums[i]那就dp[j] + 1;然后不断遍历保持最大。
if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
3.初始化dp数组
vector<int> dp(nums.size(), 1);
因为一个数也是一个递增序列
4.确定遍历顺序
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] > result) result = dp[i]; // 取长的子序列}
5.打印数组
代码实现:
int lengthOfLIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();vector<int> dp(nums.size(), 1);int result = 0;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] > result) result = dp[i]; // 取长的子序列}return result;}
第二题:
简介:
大家可以看一看第一题与第二题大的不同之处。第二题新增了一个条件:必须是连续的。所以,我们不需要去遍历数组去得到从前最大的子串长度。因为是连续的所以我们只需要知道前一个数是否小于当前数。所以递推公式为:
其他与第一题相同。
代码实现:
int findLengthOfLCIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();vector<int> dp(nums.size(), 1);int result =0;for(int i = 1; i < nums.size(); i++){if(nums[i]>nums[i-1])dp[i] = dp[i-1]+1;if(dp[i]>result)result =dp[i];}return result;}
第三题:
简介:
本题先看实例图:
一个二维数组dp[i][j]进行循环遍历,如果遇到相等值就让左上角的值加一赋给当前值,但是为什么要左上角加一赋值,因为我们可以在脑中想想如果两个完全相同的数组组成二维数组,把列和行值相同的交接处值为1,其他为零。把1连接起来是不是一条从左上到右下的对角线所以:最长重复子数组它的值dp[i][j]是由dp[i-1][j-1]计算而出的所以递推公式为:
if(nums1[i-1]==nums2[j-1]) dp[i][j] = dp[i-1][j-1]+1;
如果两值相等就让dp[i-1][j-1]加一。
动态规划五部曲:
1.确定 dp数组下标的定义
dp[i][j] :以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。
2.确定递推公式
if(nums1[i-1]==nums2[j-1]) dp[i][j] = dp[i - 1][j - 1] + 1;;
3.初始化dp数组
都初始化为零。
4.确定遍历顺序
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(dp[i][j]>result) result =dp[i][j];}}
5.打印数组
代码实现:
int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));dp[0][0] =0;int result;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(dp[i][j]>result) result =dp[i][j];}}return result;}
总结:
今天的题较有规律的题,要总结一下。继续加油!