题目

有一个由非负整数组成的三角形,第一行只有一个数,除了最下行之外每个数的左下方和右下方各有一个数,如下图:
题目
从第一行开始,每次可以往做下或右下走一格,直到走到最下行,把沿途经过的数全部加起来,如何走才能使得这个和最大。

分析

可以从下往上来分析
如下:
1
3 2
4 10 1
4 3 2 20
从下开始往上更新。

第1次更新为:
1
3 2
8 13 21
4 3 2 20

第2次更新:
1
16 23
8 13 21
4 3 2 20

第3次更新:
24
16 23
8 13 21
4 3 2 20

三种实现方法:递归、递推、记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
递归
4
1
3 2
4 10 1
4 3 2 20
*/
import java.util.Scanner;

public class Main {

static int [][]a = new int [100][100]; //用来存储数字三角形的数据
static int [][]c = new int [100][100]; //用来存路径
static int n ;
static int count;

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
int i,j;
for(i=0;i<n;i++){
for(j=0;j<=i;j++){
a[i][j] = scanner.nextInt();
}
}

System.out.println(fun(0, 0));
System.out.println("计算了"+count+"次");

//输出走的路径
System.out.print("路径如下:(0,0)");
int t = 0;
for(i=1;i<n;i++){
System.out.print("->("+i+","+c[i-1][t]+")");
t = c[i-1][t];
}

}

public static int fun(int i,int j){
if(i == n-1)
return a[i][j]; //如果到了最下面一层,就返回当前这个数
count++;

int t1 = fun(i+1, j);
int t2 = fun(i+1, j+1);
if(t1>t2){
c[i][j] = j; //表示当前这个位置是从下一行哪个数据来的
return a[i][j]+t1;
}else {
c[i][j] = j+1; //表示当前这个位置是从下一行哪个数据来的
return a[i][j]+t2;
}

//return a[i][j] + Math.max(fun(i+1, j), fun(i+1, j+1));
}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
* 递推
*/

import java.util.Scanner;

public class Main {

static int [][]a = new int [4][4];
static int [][]d = new int [4][4];
static int n ;
static int count;

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
int i,j;
for(i=0;i<n;i++){
for(j=0;j<=i;j++){
a[i][j] = scanner.nextInt();
d[i][j] = a[i][j];
}
}
for(i=n-1;i>=1;i--){
for(j=0;j<i;j++){
count++;
d[i-1][j]+=Math.max(d[i][j], d[i][j+1]);
}
}
System.out.println(d[0][0]);
System.out.println("计算了"+count+"次");

}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
* 记忆化搜索
*/


import java.util.Scanner;

public class Main {
static int [][]a = new int [100][100];
static int [][]d = new int [100][100];
static int n ;
static int count;

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
a[i][j] = scanner.nextInt();
}
}
System.out.println(fun(0, 0));
System.out.println("计算了"+count+"次");
}

public static int fun(int i,int j){
if(i == n-1)
return a[i][j]; //如果到了最下面一层,就返回当前这个数

if(d[i][j]!=0) return d[i][j];

count++; //统计 计算了多少次
d[i+1][j] = fun(i+1, j);
d[i+1][j+1] = fun(i+1, j+1);
return a[i][j] + Math.max(d[i+1][j], d[i+1][j+1]);
}

}