杭州有哪些做网站的公司好,设备技术支持东莞网站建设,品牌设计有哪些东西,中国化工网网站建设建议共性
做完下面三题#xff0c;发现三个的dp数组中i都是以 i 为结束的字串。
1 300. 最长递增子序列
300. 最长递增子序列
AC#xff1a;
class Solution {
public:int dp[10010]; // 表示以i结束的子序列最大的长度/*if(nums[j] nums[i])dp[j] max(dp[j],dp[i] …共性
做完下面三题发现三个的dp数组中i都是以 i 为结束的字串。
1 300. 最长递增子序列
300. 最长递增子序列
AC
class Solution {
public:int dp[10010]; // 表示以i结束的子序列最大的长度/*if(nums[j] nums[i])dp[j] max(dp[j],dp[i] 1);dp[0..nums.size()-1] 1;每个i结束i j 0...n-1 j模拟——*/int lengthOfLIS(vectorint nums) {for(int i 0; i nums.size();i)dp[i] 1;int ans 0;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);}ans max(ans,dp[i]);}return ans;}
};
2 674. 最长连续递增序列
674. 最长连续递增序列
和上一题差不多就是 j 直接为 i - 1 即可。AC代码
class Solution {
public:int dp[10010]; // 以i结束的子序列最长的连续递增的长度/*j i-1if(nums[i] nums[j])dp[i] max(dp[i],dp[j])dp[0...n-1] 1i j模拟——*/int findLengthOfLCIS(vectorint nums) {for(int i 0; i nums.size();i)dp[i] 1;int ans 1;for(int i 1; i nums.size();i){int j i-1;if(nums[i] nums[j])dp[i] max(dp[i],dp[j]1);ans max(ans,dp[i]);cout dp[i] ;}return ans;}
}; 前两题概括来说 不连续递增子序列的跟前0-i 个状态有关连续递增的子序列只跟前一个状态有关 3 718. 最长重复子数组
718. 最长重复子数组
重点
1.
注意题目中说的子数组暗指的是连续子序列。
2.
int dp[1010][1010]; // nums1以i结尾 nums2的以j结尾 最长公共子串的长度
以x结尾两个字串才可比较。
3.
需要重点理解dp[i][j] 只能从dp[i-1][j-1]推导出来 不能从dp[i-1][j] 或是dp[i][j-1]
carl一共在实现细节上给了三种方式我使用了dp数组含义更加直观但是多写几行的第三种写法在拓展部分AC代码
class Solution {
public:int dp[1010][1010]; // nums1以i结尾 nums2的以j结尾 最长公共子串的长度/*需要重点理解dp[i][j] 只能从dp[i-1][j-1]推导出来 不能从dp[i-1][j] 或是dp[i][j-1]if(nums[i] nums[j])dp[i][j] dp[i - 1][j - 1] 1else dp[i][j] 0for(int j 0; j nums1.size();j)if(nums2[0] nums1[i]) dp[0][j] 1else dp[0][j] 0for(int i 0; i nums2.size();i)if(nums1[0] nums2[i]) dp[i][0] 1else dp[i][0] 0;i j*/int findLength(vectorint nums1, vectorint nums2) {int ans 0;for(int j 0; j nums1.size();j){if(nums2[0] nums1[j]) dp[0][j] 1;else dp[0][j] 0;ans max(ans,dp[0][j]);}for(int i 0; i nums2.size();i){if(nums1[0] nums2[i]) dp[i][0] 1;else dp[i][0] 0;ans max(ans,dp[i][0]);}for(int i 1; i nums2.size();i){for(int j 1; j nums1.size();j){if(nums2[i] nums1[j])dp[i][j] dp[i - 1][j - 1] 1;else dp[i][j] 0;ans max(ans,dp[i][j]);}}// for(int i 0; i nums2.size();i)// {// for(int j 0; j nums1.size();j)// cout dp[i][j] ;// cout endl;// }return ans;}
};
