[PKU] 1163 -- The Triangle - 単純に再帰させるだけではだめでした。 2008/02/14

• 1163 -- The Triangle

チャレンジしてみました。

ちょっと考えて書いたコードだったのですが、案の定だめでした。

これぐらいだったら平気なのですが、最大100ですと、計算量が、2¹⁰⁰となるらしくだめ。
5だと2⁵。

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

以下だめコード。

package p1163;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
a();
}

static void a() {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();

list = new int[n][];
for (int i = 0; i < n; i++) {
int[] js = new int[i+1];

for (int j = 0; j <= i; j++) {
js[j] = scanner.nextInt();
}
list[i] = js;
}

int max = max(list[0][0], 0, 1);
System.out.println(max);
}

static int[][] list;
static int n = 0;

static int max(int c, int p, int pos) {

if (n <= pos)
return c;
int l = list[pos][p] + max(c, p, pos + 1);
int r = list[pos][p + 1] + max(c, p + 1, pos + 1);

return l < r ? r : l;
}

}