SGU 104 Little shop of flowers

제목: n 송이 꽃, m 개 꽃병.i번째 꽃을 j번째 꽃병에 꽂으면 가치cost[i][j]를 얻을 수 있습니다.i꽃은 i+1꽃 앞에 꽂아야 합니다.최대 가치를 구하고 방안을 출력하다.
분석:
최대 가치를 추구하기 위해 j번째 꽃병에 꽃을 꽂거나 꽂지 않는 두 가지 가능성을 고려하여 dp[i][j]를 설정하면 전 i송이 꽃을 전 j개 꽃병에 꽂아서 얻을 수 있는 최대 가치를 나타낸다. 그러면 상태 이동 방정식을 얻어낼 수 있다. dp[i][j]=max(dp[i][j-1], dp[i-1][j-1]+cost[i][j])이다.즉 dp[i][j]에서 제j번째 꽃병에 꽃을 꽂지 않는 것과 꽃을 꽂지 않는 비교적 큰 값을 얻는다.
출력 방안에 대해pos[i][j]로 i번째 꽃병에 꽂힌 위치를 기록합니다.출력에 귀속시키면 된다.

import java.util.Scanner;

public class Solution{
    public static int dp[][] = new int[110][110], cost[][] = new int[110][110],
            pos[][] = new int[110][110], m, n;

    public static void printf(int i, int j) {
        if (i != 1) {
            printf(i - 1, pos[i][j] - 1);
            System.out.print(" " + pos[i][j]);
        } else {
            System.out.print(pos[i][j]);
            return;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            n = in.nextInt();
            m = in.nextInt();
            int i, j;
            for (i = 1; i <= n; ++i)
                for (j = 1; j <= m; ++j)
                    cost[i][j] = in.nextInt();
            for(i=0;i<=n;++i)
                for(j=0;j<=m;++j) dp[i][j]=-200;
            for (j = 1; j <= m; ++j) {
                if (dp[1][j - 1] > cost[1][j]) {
                    dp[1][j] = dp[1][j - 1];
                    pos[1][j] = pos[1][j - 1];
                } else {
                    dp[1][j] = cost[1][j];
                    pos[1][j] = j;
                }
            }
            for (i = 2; i <= n; ++i)
                for (j = i; j <= m; ++j) {
                    if (dp[i][j - 1] > dp[i - 1][j - 1] + cost[i][j]) {
                        dp[i][j] = dp[i][j - 1];
                        pos[i][j] = pos[i][j - 1];
                    } else {
                        dp[i][j] = dp[i - 1][j - 1] + cost[i][j];
                        pos[i][j] = j;
                    }
                }
            System.out.println(dp[n][m]);
            printf(n, m);
        }
        in.close();
    }
}