피라미드 경로

다음과 같은 피라미드가 있을 때 A에서 맨 밑의 K, L, M, N, O 까지 내려오는 경로를 구하는 문제이다.
각 지점에서 왼쪽 아래 또는 오른쪽 아래로 내려갈 수 있다.
이 문제는 dp를 이용해서 해결 할 수 있다. 예를 들어 A에서 L까지 가는 경로는 A에서 G까지 가는 경로와 A에서 H까지 가는 경로를 더한 값이다.
다시 A에서 H까지 가는 경로는 A에서 D, E 까지 가는 경로를 더한 값과 같다.
이처럼 겹치는 부분문제들을 갖고 있는 문제는 dp를 이용하면 쉽게 해결할 수 있다.

피라미드를 행과 열이 각각 5인 이차원 배열에 넣는다고 생각하면 다음과 같다.

public class Main
{
    public static void solution(int m, int n)
    {
        int[][] street = new int[n][m];

        street[0][0] = 1;
        
        for (int i=1; i<n; i++)
        {
            for (int j=0; j<=i; j++)
            { // 첫 열이거나 (ABDGK)
             // ACFJO 처럼 끝 대각선인 경우
                if (j == 0 || i == j)
                    street[i][j] = 1; // 경로가 1개 밖에 없다
                else // 그렇지 않은 경우
                    street[i][j] = street[i-1][j] + street[i-1][j-1];
            }
        }
        
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<m; j++)
            {
                System.out.print(street[i][j] + " ");       
            }
            System.out.println();
        }
    }
    public static void main(String[] args) 
	{
	    int m = 5;
	    int n = 5;
	    solution(m, n);
	}
}