2013
11-09

# The Triangle

73   88   1   02   7   4   44   5   2   6   5(Figure 1)

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.

Your program is to write to standard output. The highest sum is written as an integer.

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

30

方法一:(来自:http://hi.baidu.com/maxupeng/blog/item/1709f6092ac19cc23ac76326.html)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int[] a = new int[n*(n+1)/2];
for (int i = 0; i < n; i++) {	//行
for (int j = 0; j <= i; j++) {	//列
int next = cin.nextInt();
int index = i*(i+1)/2 + j;
if (j == 0) {	//行最左边的数，父亲为index-i
a[index] = a[index] + next + a[index-i];
} else if (j == i) { //行最右边的数，父亲为index-i-1
a[index] = a[index] + next + a[index-i-1];
} else {	//行中间的数，父亲为index-i和index-i-1
a[index] = a[index] + next + Math.max(a[index-i], a[index-i-1]);
}
}
}
int max = 0;
for (int i = (n-1)*n/2; i < (n+1)*n/2; i++) {
if (a[i] > max) max = a[i];
}
System.out.println(max);
}
}

//Pku 1163 the Triangle by [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */&jlu
import java.util.StringTokenizer;

public class Main {

public static void main(String[] args) throws Exception{

int [][]number = new int[num][num];
for(int i=0;i< num;i++){
StringTokenizer strToke = new StringTokenizer(str);
for(int j=0;j<=i;j++){
number[i][j] = Integer.parseInt(strToke.nextToken());
}
}
for(int i=num-2;i>=0;i--){
for(int j=0;j<=i;j++){
number[i][j] = Math.max(number[i+1][j], number[i+1][j+1])+number[i][j];
}
}

System.out.println(number[0][0]);
}

}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮