算法笔记|Day37动态规划X
算法笔记|Day37动态规划X
- ☆☆☆☆☆leetcode 300.最长递增子序列
- 题目分析
- 代码
- ☆☆☆☆☆leetcode 674. 最长连续递增序列
- 题目分析
- 代码
- ☆☆☆☆☆leetcode 718. 最长重复子数组
- 题目分析
- 代码
☆☆☆☆☆leetcode 300.最长递增子序列
题目链接：leetcode 300.最长递增子序列
题目分析
1.dp数组含义：dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度，取所有dp[i]中的最大值即为所求最长递增子序列的长度；
2.递推公式：if(nums[i]>nums[j])dp[i]=Math.max(dp[j]+1,dp[i])（如果遍历j从0到i-1，对所有满足nums[i]>nums[j]的j取dp[j]+1的最大值）；
3.初始化：所有dp[i]=1（每一个i最长递增子序列大小至少都是1）；
4.遍历顺序：从小到大。
代码
class Solution {public int lengthOfLIS(int[] nums) {int dp[]=new int[nums.length];int res=1;for(int i=0;i<nums.length;i++)dp[i]=1;for(int i=0;i<nums.length;i++){for(int j=0;j<i;j++){if(nums[i]>nums[j])dp[i]=Math.max(dp[j]+1,dp[i]);res=Math.max(dp[i],res);}}return res;}
}
☆☆☆☆☆leetcode 674. 最长连续递增序列
题目链接：leetcode 674. 最长连续递增序列
题目分析
1.dp数组含义：dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度，取所有dp[i]中的最大值即为所求最长连续递增序列的长度；
2.递推公式：if(nums[i]>nums[i-1])dp[i]=dp[i-1]+1（如果nums[i]>nums[i-1]，则取dp[i-1]+1）；
3.初始化：所有dp[i]=1（每一个i最长递增子序列大小至少都是1）；
4.遍历顺序：从小到大。
代码
class Solution {public int findLengthOfLCIS(int[] nums) {int dp[]=new int[nums.length];int res=1;for(int i=0;i<nums.length;i++)dp[i]=1;for(int i=1;i<nums.length;i++){if(nums[i]>nums[i-1])dp[i]=dp[i-1]+1;res=Math.max(dp[i],res);}return res;}
}
☆☆☆☆☆leetcode 718. 最长重复子数组
题目链接：leetcode 718. 最长重复子数组
题目分析
1.dp数组含义：dp[i][j]表示以nums1[i-1]和nums2[j-1]为结尾的最长重复子数组长度，取所有dp[i][j]中的最大值即为所求最长重复子数组的长度；
2.递推公式：if(nums1[i-1]==nums2[j-1])dp[i][j]=dp[i-1][j-1]+1（如果结尾元素相等，dp[i][j]在dp[i-1][j-1]的基础上加一）；
3.初始化：所有dp[i][0]=0，所有dp[0][j]=0；
4.遍历顺序：从小到大。
代码
class Solution {public int findLength(int[] nums1, int[] nums2) {int dp[][]=new int[nums1.length+1][nums2.length+1];int res=0;for(int i=1;i<=nums1.length;i++){for(int j=1;j<=nums2.length;j++){if(nums1[i-1]==nums2[j-1])dp[i][j]=dp[i-1][j-1]+1;res=Math.max(dp[i][j],res);}}return res;}
}