着重理解else里面的逻辑
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int len1 = text1.length();
int len2 = text2.length();
//到i-1 j-1的最长公共子序列
int [][] dp = new int[len1+1][len2+1];
//定义i-1 j-1不用初始化
int res = Integer.MIN_VALUE;
for(int i = 1;i<=len1;i++){
for(int j = 1;j<=len2;j++){
//递推公式
if(text1.charAt(i-1)==text2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] +1;
}else{
dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
}
res = Math.max(res,dp[i][j]);
}
}
return res;
}
}
本质和上题一样
class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int [][] dp = new int[len1+1][len2+1];
for(int i = 1;i<=len1;i++){
for(int j = 1;j<=len2;j++){
if(nums1[i-1]==nums2[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[len1][len2];
}
}
? ?
秒了,动态规划的比贪心的简单
class Solution {
public int maxSubArray(int[] nums) {
if(nums.length==1) return nums[0];
//以i为结尾的最大子序和
int [] dp = new int[nums.length];
dp[0] = nums[0];
int res = nums[0];
for(int i = 1;i<nums.length;i++){
dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
res = Math.max(res,dp[i]);
}
return res;
}
}