dp 路径记录
作者:
goldstine
,
2022-04-26 22:39:22
,
所有人可见
,
阅读 180
三个无重叠子数组的最大和
三个无重叠子数组的和
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
//通过dp的方式输出
int n=nums.length;
//前缀和
int[] prefix=new int[n+1];
for(int i=1;i<=n;i++){
prefix[i]=prefix[i-1]+nums[i-1];
}
int[][] dp=new int[n+2][4];//dp[i][j]表示i开始后面的数组元素,划分不重叠的j组元素,最大和为dp[i][j]
int x=n+1;
for(int i=n-k+1;i>0;i--){
for(int j=1;j<=3;j++){
dp[i][j]=Math.max(dp[i+1][j],dp[i+k][j-1]+prefix[i+k-1]-prefix[i-1]);
}
if(dp[i][3]>=dp[x][3]){//将最大的位置记录下来
x=i;
}
}
int index=0;
int[] res=new int[3];
for(int j=3;j>=1;j--){
while(dp[x][j]!=dp[x+k][j-1]+prefix[x+k-1]-prefix[x-1]){x++;}
res[index++]=x-1;
x+=k;
}
return res;
}
}
输出最长公共子序列
输出最长公共子序列
class Solution {
public String shortestCommonSupersequence(String str1, String str2) {
int n=str1.length();int m=str2.length();
int[][] dp=new int[n+1][m+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(str1.charAt(i-1)==str2.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]);
}
}
}
//将最长公共子序列输出
// StringBuilder s=new StringBuilder();
// int start=n;int end=m;
// while(dp[start][end]>0){
// if(str1.charAt(start-1)==str2.charAt(end-1)){
// s.append(str1.charAt(start-1));
// start--;end--;
// }else{
// if(dp[start][end-1]>=dp[start-1][end]){
// end--;
// }else{
// start--;
// }
// }
// }
// s.reverse();
// System.out.println(s.toString());
StringBuilder sb=new StringBuilder();
int i=n;int j=m;
while(dp[i][j]>0){
if(str1.charAt(i-1)==str2.charAt(j-1)){
sb.append(str1.charAt(i-1));
i--;j--;
}else{
if(dp[i-1][j]>=dp[i][j-1]){
sb.append(str1.charAt(i-1));
i--;
}else{
sb.append(str2.charAt(j-1));
j--;
}
}
}
for(int k=i;k>0;k--){
sb.append(str1.charAt(k-1));
}
for(int k=j;k>0;k--){
sb.append(str2.charAt(k-1));
}
sb.reverse();
return sb.toString();
}
}