Learning Journal

2/16/2024

Coin Change

Tags: algorithms leetcode dynamic_programming

function coinChange(coins: number[], amount: number): number {
    if(amount === 0) return 0;

    const leastCoinsArr:number[] = Array(amount + 1);

    leastCoinsArr[0] = 0;


    for(let curI = 1; curI < leastCoinsArr.length; curI++) {
        let min = Number.POSITIVE_INFINITY;

        for(let i = 0; i < coins.length; i++) {
            if(curI - coins[i] >= 0) {
                if(min > 1 + leastCoinsArr[curI - coins[i]])
                    min = 1 + leastCoinsArr[curI - coins[i]];
            }
        }

        leastCoinsArr[curI] = min;
    }

    return leastCoinsArr[amount] === Number.POSITIVE_INFINITY? -1 : leastCoinsArr[amount];
};function coinChange(coins: number[], amount: number): number {
    if(amount === 0) return 0;

    const leastCoinsArr:number[] = Array(amount + 1);

    leastCoinsArr[0] = 0;


    for(let curI = 1; curI < leastCoinsArr.length; curI++) {
        let min = Number.POSITIVE_INFINITY;

        for(let i = 0; i < coins.length; i++) {
            if(curI - coins[i] >= 0) {
                if(min > 1 + leastCoinsArr[curI - coins[i]])
                    min = 1 + leastCoinsArr[curI - coins[i]];
            }
        }

        leastCoinsArr[curI] = min;
    }

    return leastCoinsArr[amount] === Number.POSITIVE_INFINITY? -1 : leastCoinsArr[amount];
};

THE PROBLEM

I just realized that there are always three steps in dynamic programming. The first step is to find a recursive solution for the problem, the second step is to use hash table to memoise the result of some recursive call to save time, and the final step is to realize that why don't we just build the hash table from the beginning and return the value in the table the corresponding to the original parameter (the first recursive call) of the function.

Revised by ChatGPT

Dynamic programming typically involves three key steps:

Identify a Recursive Solution: Start by finding a recursive solution to the problem. This often involves breaking down the problem into smaller, more manageable subproblems.
Memoization: To avoid redundant calculations and improve efficiency, use a hash table (or another data structure) to store the results of recursive calls. This technique is known as memoization.
Bottom-Up Approach: Instead of starting with the original problem and breaking it down, build up the solution from the base cases. This involves filling out a table (or array) based on the recursive relationships, starting from the simplest subproblems. The final answers can then be directly obtained from this table, corresponding to the original parameters of the problem.

By following these steps, dynamic programming provides a systematic approach to solving complex problems by combining the solutions to smaller subproblems.