Programmers_389480.java

package programmers.lv2;

import java.util.Arrays;

public class Programmers_389480 {
    public static void main(String[] args) {
        Programmers_389480 test = new Programmers_389480();
        int[][] info = { { 1, 2 }, { 2, 3 }, { 2, 1 } };
        int n = 4;
        int m = 4;
        int result = test.solution(info, n, m);
        System.out.println("result: " + result);
    }

    public int solution(int[][] info, int n, int m) {
        int len = info.length;
        int maxValue = Integer.MAX_VALUE;
        int[][] dp = new int[len + 1][m];
        for (int i = 0; i <= len; i++) {
            Arrays.fill(dp[i], maxValue);
        }
        dp[0][0] = 0;

        for (int i = 1; i <= len; i++) {
            int a = info[i - 1][0];
            int b = info[i - 1][1];

            for (int j = 0; j < m; j++) {
                if (dp[i - 1][j] == maxValue)
                    continue;

                int nextA = dp[i - 1][j] + a;
                if (nextA < n) {
                    dp[i][j] = Math.min(nextA, dp[i][j]);
                }

                int nextB = j + b;
                if (nextB < m) {
                    dp[i][nextB] = Math.min(dp[i][nextB], dp[i - 1][j]);
                }
            }
        }

        // System.out.println();
        // for (int i = 0; i <= len; i++) {
        // for (int j = 0; j < m; j++) {
        // System.out.print(dp[i][j] + " ");
        // }
        // System.out.println();
        // }

        int answer = maxValue;
        for (int j = 0; j < m; j++) {
            answer = Math.min(answer, dp[len][j]);
        }

        return answer == maxValue ? -1 : answer;
    }
}