(알고스팟)TRIPATHCNT

숫자로 이루어진 삼각형이 주어졌을 때, 최대경로 합의 갯수를 구하기
단, 아래 또는 오른쪽 대각선으로만 움직 일 수 있다.

count(y,x)=(y,x)에서 시작해 맨 아래줄까지 내려가는 최대 경로의 수


                       count(y+1,x) (path2(y+1,x)>path2(y+1,x+1))
count(y,x)=max(  count(y+1,x+1)  (path2(y+1,x+1)>path2(y+1,x))
                       count(y+1,x+1)+count(y+1,x)   (path2(y+1,x+1)==path2(y+1,x))



--->>> 중요한 점 삼각형 경로에서 path(y+1,x+1)과 path(y+1,x)의 크기를 비교 할 때
단순기 경로사의 수를 비교하는 게 아니라 경로상의 최대합의 크기를 비교해야 한다.
그 이유는 만약 바로 다음 경로의 크기가 작다고 하더라도 다다음의 크기가 압도적으로 클 수 있다. 
   (a)        |     (b)
9             |    24
5 7          |     13  15
1 3 2        |     6    8   8
3 5 5 6     |     3     5   5   6
<경로>          <경로길이의 합>
public class TRIPATHCNT {

private static int cache[][]=new int[100][100];
private static int Countcache[][]=new int[100][100];
private static int panel[][];
private static int N;

public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub

BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
N=Integer.parseInt(reader.readLine());
panel=new int[N+1][N+1];

for(int i=0;i<N;i++)
{
String k=reader.readLine();
for(int j=0;j<k.length();j++){
panel[i][j]=k.charAt(j)-48;
}
}
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++){
System.out.print(panel[i][j]+",");
}
System.out.println();
}

for(int[] row:cache)
Arrays.fill(row, -1);
for(int[] row:Countcache)
Arrays.fill(row, -1);

System.out.println(count(0,0));
}

private static int count(int y,int x)
{
if(y==N-1)return 1;


if(Countcache[y][x]!=-1)return Countcache[y][x];

int ret=0;
if(path(y+1,x)>=path(y+1,x+1))ret+=count(y+1,x);
if(path(y+1,x+1)>=path(y+1,x))ret+=count(y+1,x+1);

return Countcache[y][x]=ret;

}
public static int path(int y,int x)
{
if(y==N-1)
return panel[y][x];
if(cache[y][x]!=-1)
return cache[y][x];

return cache[y][x]=panel[y][x]+Math.max(path(y+1,x+1),path(y+1,x));

}

}