盐城永祥建设有限公司网站,怎么用dw网站怎么建设,怎么给网站做php后台,影楼公共网站300.最长递增子序列
这道题目的重点在于动态数组的定义 dp[i]#xff1a;以nums[i]为结尾的最长递增子序列#xff0c;因为这样定义可以进行递推#xff1b; 递推#xff1a;j从0-i进行对比#xff0c;如果nums[i]大于nums[j]#xff0c;dp[i]dp[j]1#xff1b; 初始化…300.最长递增子序列
这道题目的重点在于动态数组的定义 dp[i]以nums[i]为结尾的最长递增子序列因为这样定义可以进行递推 递推j从0-i进行对比如果nums[i]大于nums[j]dp[i]dp[j]1 初始化所有的元素向初始化为1 遍历顺序从前到后 详细代码如下 class Solution {
public:
int lengthOfLIS(vectorint nums)
{if(nums.size()0) return 0;vectorintdp(nums.size(), 1); //init as 1int max_len 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);}max_len max(max_len, dp[i]);}return max_len;
}
}; 674. 最长连续递增序列 这道题的相比上一题因为是连续递增所以只需要和前一个num[i-1]相比即可不再进行详细分析详细代码如下 class Solution {
public:
int findLengthOfLCIS(vectorint nums)
{if(nums.size()0) return 0;vectorintdp(nums.size(), 1);int max_len 1;for(int i 1; i nums.size(); i) {if (nums[i] nums[i - 1]) dp[i] dp[i - 1] 1;max_len max(max_len, dp[i]);}return max_len;
}}; 718. 最长重复子数组
这道题是对两个数组进行判断因此需要二维数组分析如下
dp[i][j]以A[i-1]为结尾和以B[j-1]为结尾的数组的最长重复子数组长度i-1的结尾的原因是这样初始化方便写而不需要进行额外的判断。
递推如果两个值相等则dp[i][j]dp[i-1][j-1]
初始化根据递推公式dp[0][0]应该是0否则后续就无法得到想要的状态结果
遍历进行两层嵌套从前往后即可
详细代码如下
class Solution {
public:
int findLength(vectorint nums1, vectorint nums2)
{//二维dp//dp[i][j]:以A的i-1结尾B的j-1结尾的最长重复长度//注意这里是为了初始化更方便vectorvectorintdp(nums1.size()1, vectorint(nums2.size() 1, 0));int max_len 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;max_len max(max_len, dp[i][j]);}}return max_len;
}}; 注意上述代码可以进行空间优化因为dp[i][j]仅和左上角元素有关所以可以压缩维度把i维度压缩运用滚动数组即可要注意的是同01背包问题一样为了不把数据踩踏里层的循环需要逆向这样就不会篡改上一层的数据导致错误。 详细代码如下 class Solution {
public:
int findLength(vectorint nums1, vectorint nums2)
{vectorintdp(nums2.size() 1, 0); //压缩第一个维度int max_len 0;for (int i 1; i nums1.size(); i) {for (int j nums2.size(); j 1; j--) //防止踩踏数据{if (nums1[i - 1] nums2[j - 1]) dp[j] dp[j - 1] 1;else dp[j] 0; //不相等需要赋值以便下次使用max_len max(max_len, dp[j]);}}return max_len;}
