1）
/** * 动态规划 * 给定一个三角形，求一条从顶部到底部的路径，这条路径所有元素和最大，输出最大值 * * 递归求法，求子问题，写递推公式，缺点是存在重复计算，时间复杂度较大，可能超时 */ package dp; import java.util.Scanner; public class Main { /** * 7 * 3 8 * 8 1 0 * 2 7 4 4 * 4 5 2 6 5 */ static int n = 0;//行数 static int[][] t = null; public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt();//总行数 t = new int[n+1][n+1];//使用二维数组存储三角形 for(int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ t[i][j] = in.nextInt(); } } //写出递推公式 //一般情况：maxSum(i, j) = max{maxSum(i+1, j), maxSum(i+1, j+1)}+t(i, j) 递归给子问题，要么往下走，要么往右下走，取最大的结果加上自己的值就是当前位置所求的值 //边界条件:maxSum(n, j) = t(n, j) 最后一行无法继续再往下或者右下走 //最后题目变成求解maxSum(1, 1) = ? //写递归函数 maxSum(int i, int j)求出从t[i][j]位置到底部的路径的最大和 System.out.println(maxSum(1, 1)); } public static int maxSum(int i, int j){ if(i == n) return t[i][j]; else return Math.max(maxSum(i+1, j), maxSum(i+1, j+1)) + t[i][j]; //递归子问题求解 } } //由于递归存在大量的重复计算，所以需要优化，思路是时间换取空间 /** * 动态规划 * 给定一个三角形，求一条从顶部到底部的路径，这条路径所有元素和最大，输出最大值 * * 递归求法，求子问题，写递推公式，缺点是存在重复计算，时间复杂度较大，可能超时（优化） * 优化思路： * 因为存在重复计算，即前边已经算过某点的最大和，后边需要改点的最大和时重复计算改点，所以使用空间换时间，将改点的计算结果保存下来 * 下次使用是不用计算，直接读值即可 */ package dp; import java.util.Scanner; public class Main { /** * 7 * 3 8 * 8 1 0 * 2 7 4 4 * 4 5 2 6 5 */ static int n = 0;//行数 static int[][] t = null;//使用二维数组存储三角形 static int[][] maxSum = null;//记录每个点的最大和 public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt();//总行数 t = new int[n+1][n+1]; maxSum = new int[n+1][n+1]; for(int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ t[i][j] = in.nextInt(); maxSum[i][j] = -1;//初始值 } } //写出递推公式 //一般情况：maxSum(i, j) = max{maxSum(i+1, j), maxSum(i+1, j+1)}+t(i, j) 递归给子问题，要么往下走，要么往右下走，取最大的结果加上自己的值就是当前位置所求的值 //边界条件:maxSum(n, j) = t(n, j) 最后一行无法继续再往下或者右下走 //最后题目变成求解maxSum(1, 1) = ? //写递归函数 maxSum(int i, int j)求出从t[i][j]位置到底部的路径的最大和 System.out.println(maxSum(1, 1)); } public static int maxSum(int i, int j){ //递归时，首先看是否已经存在改点的最大和，可以直接返回 if(maxSum[i][j] != -1) return maxSum[i][j]; if(i == n) return t[i][j]; else{ //递归子问题求解 maxSum[i][j] = Math.max(maxSum(i+1, j), maxSum(i+1, j+1)) + t[i][j]; return maxSum[i][j]; } } } /** * 动态规划 * 给定一个三角形，求一条从顶部到底部的路径，这条路径所有元素和最大，输出最大值 * * 继续优化 * 由于使用递归，会使用大量的栈空间，容易造成栈溢出，所以可以将其改成递推型动态规划，因为第n行路径最大和已经确定，即从第n-1行开始向上递推出每个点的路径最大和 */ package dp; import java.util.Scanner; public class Main { /** * 7 * 3 8 * 8 1 0 * 2 7 4 4 * 4 5 2 6 5 */ static int n = 0;//行数 static int[][] t = null;//使用二维数组存储三角形 static int[][] maxSum = null;//记录每个点的最大和 public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt();//总行数 t = new int[n+1][n+1]; maxSum = new int[n+1][n+1]; for(int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ t[i][j] = in.nextInt(); if(i ==n){ //第n行的点就是其路径的最大和 maxSum[i][j] = t[i][j]; } } } //开始从下网上递推，求出每个点的路径最大和，依然使用递归公式，这里应该叫做动态转移公式 for(int i = n-1; i >= 1; i--){//从第n-1行开始向上递推 for(int j = 1; j <= i; j++){//递推时，依次递推当前行的每个点 maxSum[i][j] = Math.max(maxSum[i+1][j], maxSum[i+1][j+1]) + t[i][j];//始终根当前行的下一行有关 } } //输出结果 System.out.println(maxSum[1][1]); } }2）
/** * 动态规划 * 给定一个三角形，求一条从顶部到底部的路径，这条路径所有元素和最大，输出最大值 * * 继续优化 * 上面的程序还可以继续优化，因为我们使用了二维数组来维护路径的最大和,其实是可以使用一维数组来记录的 * 向上递归的时候，我们始终只要存储当前行的每个点的最大路径的和，将以前的覆盖就行，这样就只需要一维数组了 */ package dp; import java.util.Scanner; public class Main { /** * 7 * 3 8 * 8 1 0 * 2 7 4 4 * 4 5 2 6 5 */ static int n = 0;//行数 static int[][] t = null;//使用二维数组存储三角形 static int[] maxSum = null;//记录每个点的最大和 public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt();//总行数 t = new int[n+1][n+1]; maxSum = new int[n+1]; for(int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ t[i][j] = in.nextInt(); if(i ==n){ //第n行的点就是其路径的最大和 maxSum[j] = t[i][j]; } } } //开始从下网上递推，求出每个点的路径最大和，每个点递推出来的结果覆盖同一个一维数组的相同的位置上 for(int i = n-1; i >= 1; i--){//从第n-1行开始向上递推 for(int j = 1; j <= i; j++){//递推时，依次递推当前行的每个点 maxSum[j] = Math.max(maxSum[j], maxSum[j+1]) + t[i][j];//始终根当前行的下一行有关 } } //输出结果 System.out.println(maxSum[1]); } }