package src.dp;

import java.util.Arrays;

/**
 * 空間優化
 * The time complexity is O(coins.length · targetVal) and the space complexity is O(targetVal).
 * @author sam
 *
 */
public class DP_myOwnImpl_Space {
    public static void main(String[] args) {
        int[] coins = { 3, 4 };
        int targetVal = 7;
        long[] resultRow = solution01(coins, targetVal);
        System.out.println("final result list: " + Arrays.toString(resultRow));
        System.out.println("final result: " + resultRow[resultRow.length - 1]);
    }

    private static long[] solution01(int[] coins, int targetVal) {

        // 初始化紀錄過程用map
        long[] resultMap = new long[targetVal + 1]; // 0的狀況都要考慮進去
        Arrays.fill(resultMap, -1);

        // 確保硬幣面值有小排到大
        Arrays.sort(coins);

        // 當沒有任何零錢時，所有結果都是無限個硬幣才能達到目標
        for (int currTargetVal = 1; currTargetVal <= targetVal; currTargetVal++) {
            int currCoinIndex = 0;
            resultMap[currTargetVal] = Integer.MAX_VALUE;
            printAry(resultMap,currTargetVal);
        }

        // 當沒有任何零錢時 + 當目標值為零時
        resultMap[0] = 0;
        printAry(resultMap,0);

        // 觀念1: 由小到大算 -> 先由只有一個硬幣的狀況開始，並記錄其最佳化結果，再來使用兩個硬幣，利用之前的結果來計算下去，再來同時用三個、四個，一直到結束
        // 觀念2: 除了第一排只能往左走以外，其餘的每一格皆可以考慮要往上走or往左走
        for (int currCoinIndex = 1; currCoinIndex <= coins.length; currCoinIndex++) {
            int currCoinVal = coins[currCoinIndex - 1];
            for (int currTargetVal = 1; currTargetVal <= targetVal; currTargetVal++) {
                // 若 當下使用的硬幣面值 > 當前的目標值, 則到表這個硬幣根本不能用，其結果將會等於使用小於此硬幣面值中最大者的結果
                if (currCoinVal > currTargetVal) {
                    resultMap[currTargetVal] = resultMap[currTargetVal];
                    printAry(resultMap, currTargetVal);
                    // 若不是，則可以選擇要取當前硬幣面值來用，或者不要 -> 兩條路下去，取其中所需硬幣數最小者
                } else {
                    resultMap[currTargetVal] = Math.min(resultMap[currTargetVal], resultMap[currTargetVal - currCoinVal] + 1);
                    printAry(resultMap, currTargetVal);
                }
            }
        }

        return resultMap;
    }

    /** 以下為講解用，非正式解題流程 **/

    private static void printAry(long[] resultMap, int targetCol) {
        for (int i = 0; i < resultMap.length; i++) {
            if (Long.compare(i, targetCol) == 0) {
                System.out.printf("%14d*", resultMap[i]);
            }else {
                System.out.printf("%15d", resultMap[i]);
            }
        }
        System.out.println();
    }
}