作者:lx比比2502869217 | 来源:互联网 | 2023-10-10 10:19
试题算法训练数字三角形废话不说直接开搞i.第一次递归方法的代码staticvoiddigui(intindex,intsum){System.out.println(sum)
试题 算法训练 数字三角形
废话不说直接开搞
i. 第一次递归方法的代码
static void digui(int index,int sum){System.out.println(sum);if(index==arr.length+1){if(sum>max){max = sum;}}else{for (int i = 0; i < index; i++) {sum+=arr[index-1][i];digui(index+1,sum);}}}
问题是最后一次进入递归不是想象中的直接回去后再进来 sum的值没有撤回
ii. 第二次方法的代码
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int a = sc.nextInt();int max = 0;int[][] arr = new int[a][a];for (int i = 0; i < a; i++) {for (int j = 0; j < i+1; j++) {arr[i][j] = sc.nextInt(); }}for (int i = 1; i < arr.length; i++) {for (int j = 0; j < i+1; j++) {if(j==0){arr[i][j] += arr[i-1][j];}else{arr[i][j]+=arr[i-1][j-1]>arr[i-1][j]?arr[i-1][j-1]:arr[i-1][j];}}}for (int i = 0; i < a; i++) {if(arr[a-1][i]>max){max = arr[a-1][i];}}System.out.println(max);}
}
思路是只需要在每层求出该位置的最大值可能就可以了