asp网站开发的实训报告,免费网站模板 带后台,手机必备app,怎么去推广一个网站Day53 动态规划 part14
1143.最长公共子序列
我的思路#xff1a; 模仿昨天的最大重复子序列长度的思路#xff0c;可以列出如下状态转移方程 对着状态转移方程写代码即可#xff0c;还是需要注意#xff0c;i, j是从1开始的#xff0c;比较的时候是str1[i -1]和str2[j…Day53 动态规划 part14
1143.最长公共子序列
我的思路 模仿昨天的最大重复子序列长度的思路可以列出如下状态转移方程 对着状态转移方程写代码即可还是需要注意i, j是从1开始的比较的时候是str1[i -1]和str2[j - 1]
解答
class Solution {public int longestCommonSubsequence(String text1, String text2) {int[][] dp new int[text1.length() 1][text2.length() 1];int maxlen 0;char[] str1 text1.toCharArray();char[] str2 text2.toCharArray();for(int i 1; i text1.length(); i) {for(int j 1; j text2.length(); j) {if(str1[i - 1] str2[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]);}if(dp[i][j] maxlen) {maxlen dp[i][j];}}}return maxlen;}
}1035.不相交的线
我的思路 这道题代码和上一题几乎一样不过只要取出dp[nums1.length][nums2.length]就是最终答案了 因为我们明确dp数组的含义 dp[i][j]表示nums1的前i个元素和nums2的前j个元素之间的最长不相交子序列的长度 那么dp[nums1.length][nums2.length]就是nums1的元素和nums2最长不相交子序列长度也就是我们需要的结果
解答
class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int[][] dp new int[nums1.length 1][nums2.length 1];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;}else {dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]);}} }return dp[nums1.length][nums2.length];}
}53. 最大子序和
我的思路 我想了一下当时贪心好像就是用的数组存放其实那会思路就是动规了 dp[i]表示的含义是当前位置之前连续数组的最大和 状态转移方程如下: 最后dp数组中最大值就是最大子序和
解答
class Solution {public int maxSubArray(int[] nums) {if(nums.length 1) {return nums[0];}int[] dp new int[nums.length];dp[0] nums[0];int maxSum dp[0];for(int i 1; i nums.length; i) {dp[i] Math.max(nums[i], dp[i - 1] nums[i]);if(dp[i] maxSum) {maxSum dp[i];}}return maxSum;}
}
