AcWing 898. 数字三角形
1.题目
2.思路
DP问题首先考虑状态转移方程，定义一个集合f ( i , j) ，表示从第一个数字（1,1）走到第 i行，第 j列（i , j）的所有方案的集合，那么我们要求的就是其中方案的整数之和的最大值。
这个点可以由左上方(i−1 , j)走过来，即f( i-1, j)+a(i , j)
这个点也可以由右上方(i−1,j−1)走过来，即f( i-1, j-1)+a(i , j)
所以状态转移方程就是f（i , j）=max{ f( i-1, j) , f( i-1, j-1) } + a(i , j)
这个思路是从上往下算，当向下走的时候，需要考虑边界问题。也就是对于f[2][1]的时候，f[1]f[0]并没有设置这个值，默认为0，题中的数字有负数，则会出现错误的最大值。需要对于f进行重置，置为Integer.MIN_VALUE，同样也可以从下往上算
3.Ac代码
思路一
import java.util.Arrays; import java.util.Scanner; public class Main { static int N=510; static int [][]a=new int[N][N]; //存储每一层数字 static int [][]f=new int[N][N]; //从第一个数字走到第 i行，第 j列元素的方案集合 public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); for (int i = 1; i <=n; i++) { for (int j = 1; j <=i; j++) { a[i][j]=sc.nextInt(); } } //因为可能这个数的上面左右两边都没有数，添加一个默认值 for (int i = 0; i <=n; i++) { for (int j = 0; j <=i+1; j++) { f[i][j]=Integer.MIN_VALUE; } } //第一个方案只有这一种情况 f[1][1]=a[1][1]; for (int i=2; i<=n; i++){ for(int j=1;j<=i;j++){ f[i][j]=Math.max(f[i-1][j-1],f[i-1][j]) + a[i][j]; } } int res=Integer.MIN_VALUE; for(int i=1;i<=n;i++){ res=Math.max(res,f[n][i]); } System.out.println(res); } }
思路二
import java.util.Arrays; import java.util.Scanner; public class Main { static int N=510; static int [][]a=new int[N][N]; //存储每一层数字 static int [][]f=new int[N][N]; //从第一个数字走到第 i行，第 j列元素的方案集合 public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); for (int i = 1; i <=n; i++) { for (int j = 1; j <=i; j++) { a[i][j]=sc.nextInt(); } } for (int i = n; i >= 1; i--) { //从最后一排开始走，从下往上。 for (int j = 1; j <= i; j++) { f[i][j] = Math.max(f[i + 1][j + 1], f[i + 1][j]) + a[i][j]; } } System.out.println(f[1][1]); } }
AcWing 895. 最长上升子序列
1.题目
2.思路
首先还是考虑状态表示，定义一个fi 表示从第一个数开始算，以第 i个数结尾的最长上升子序列，如果我们选第1个数，那么对应的就是f1
如果我们选第2个数，那么对应的就是f2
如果我们选第j个数，那么对应的就是f j
所以状态转移方程就是f i=max （f i +1)
3.Ac代码
import java.util.Scanner; public class Main { static int N=1010; static int []a=new int[N]; //存储数组 static int []f=new int[N]; //fi 表示从第一个数开始算，以第 i个数结尾的最长上升子序列 public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); for (int i = 1; i <=n; i++) { a[i]=sc.nextInt(); } int res=0; for (int i = 1; i <=n; i++) { f[i]=1; for (int j = 1; j < i; j++) { if(a[j]<a[i]){ f[i]=Math.max(f[i],f[j]+1); } } res=Math.max(res,f[i]); } System.out.println(res); } }
感谢你能看完，如果对你有帮助的话，点个赞支持下
