Dynamic Programming

70. Maximum Subarray

TODO

71. 322. Coin Change

class Solution {
    public int coinChange(int[] coins, int amount) {
        // Unknown: -1; Yes: 1; No: 0
        int[] dp = new int[amount+1];
        Arrays.fill(dp, -1);
        int result = helper(coins, amount, dp);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    private int helper(int[] coins, int amount, int[] dp) {
        if (amount == 0) {
            return 0;
        }

        if (amount < 0) {
            return Integer.MAX_VALUE;
        }

        if (dp[amount] != -1) {
            return dp[amount];
        }

        int steps = Integer.MAX_VALUE;
        for (int coin : coins) {
            int ans = helper(coins, amount - coin, dp);

            if (ans != Integer.MAX_VALUE) {
                steps = Math.min(ans + 1, steps);
            }
        }

        dp[amount] = steps;
        return dp[amount];
    }
}

72. 70. Climbing Stairs

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
 * <a href="https://leetcode.com/problems/climbing-stairs/">70. Climbing Stairs</a>
 */
class ClimbStairs {

    /**
     * f(n) = f(n-1) + f(n-2)
     * f(1) = 1
     * f(0) = 1
     *
     * @param n
     * @return
     */
    public int climbStairs(final int n) {
        if (n == 1 || n == 0) {
            return 1;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    public int climbStairs2(final int n) {
        return climbStairsBetter(n)[0];
    }

    /**
     * remove the tail recursive
     *
     * @param n
     * @return
     */
    public int[] climbStairsBetter(final int n) {
        if (n <= 1) {
            return new int[]{n, 1};
        }
        final int[] temp = climbStairsBetter(n - 1);
        return new int[]{temp[0] + temp[1], temp[0]};
    }

    public int climbStairsDp(final int n) {
        final int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    @Test
    void given2Stairs_whenCheckMethods_thenItShouldBe2() {
        final int n = 2;
        final int output = 2;
        Assertions.assertEquals(output, climbStairs(n));
        Assertions.assertEquals(output, climbStairs2(n));
        Assertions.assertEquals(output, climbStairsDp(n));
    }

    @Test
    void given3Stairs_whenCheckMethods_thenItShouldBe3() {
        final int n = 3;
        final int output = 3;
        Assertions.assertEquals(output, climbStairs(n));
        Assertions.assertEquals(output, climbStairs2(n));
        Assertions.assertEquals(output, climbStairsDp(n));
    }

    @Test
    void given10Stairs_whenCheckMethodsUsingDifferentAlgo_thenTheResultShouldMatch() {
        final int n = 10;
        Assertions.assertEquals(climbStairs(n), climbStairsDp(n));
    }
}

73. Partition Equal Subset Sum

TODO

74. Unique Paths

TODO

55. Jump Game

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
 * <a href="https://leetcode.com/problems/jump-game/">55. Jump Game</a>
 * <a href="https://mp.weixin.qq.com/s?__biz=Mzg4OTYzODM4Mw==&mid=2247485685&idx=1&sn=71d39243bccdb9023f7ce55f4948a66c&chksm=cfe99475f89e1d63e598bc3c15e44b23b2f24dffbced86fbfa404fba9ea340fc389bac179af4#rd">来见识一下贪心算法：Jump Game</a>
 */
class JumpGame {
    public boolean canJump(final int[] nums) {
        final int size = nums.length;
        if (size == 0 || size == 1)
            return true;
        int step = nums[0];
        for (final int num : nums) {
            step = Math.max(step - 1, num);
            if (step <= 0)
                return false;
        }
        return true;
    }

    @Test
    void giveInput1_whenCheckTheResult_thenItShouldBeTrue() {
        final int[] nums = new int[]{2, 3, 1, 1, 4};
        final boolean output = true;
        Assertions.assertEquals(output, canJump(nums));
    }

    @Test
    void giveInput2_whenCheckTheResult_thenItShouldBeFalse() {
        final int[] nums = new int[]{3, 2, 1, 0, 4};
        final boolean output = false;
        Assertions.assertEquals(output, canJump(nums));
    }
}

Maximum Gold

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

class MaximumGold {
    public int getMaximumGold(final int w, final int n, final int[] p, final int[] g) {
        final int[][] result = new int[n + 1][w + 1];
        for (int i = 1; i <= n; i++) { // num of mines
            for (int j = 1; j <= w; j++) { // num of workers
                if (j < p[i - 1]) {
                    result[i][j] = result[i-1][j];
                } else {
                    result[i][j] = Math.max(result[i - 1][j], result[i - 1][j - p[i - 1]] + g[i - 1]);
                }
            }
        }

        return result[n][w];
    }

    public int getMaximumGoldV2(final int w, final int n, final int[] p, final int[] g) {
        final int[] result = new int[w + 1];
        for (int i = 1; i <= n; i++) { // num of mines
            for (int j = w; j >= 1; j--) { // num of workers, note here we should calculate from right to left
                if (j >= p[i - 1]) {
                    result[j] = Math.max(result[j], result[j - p[i - 1]] + g[i - 1]);
                }
            }
        }
        return result[w];
    }


    @Test
    void testMaximumGoldOne() {
        final int w = 10;
        final int n = 5;
        final int[] p = new int[]{5, 5, 3, 4, 3};
        final int[] g = new int[]{400, 500, 200, 300, 350};
        final int output = 900;
        Assertions.assertEquals(output, getMaximumGold(w, n, p, g));
    }

    @Test
    void testMaximumGoldTwo() {
        final int w = 10;
        final int n = 5;
        final int[] p = new int[]{5, 5, 3, 4, 3};
        final int[] g = new int[]{400, 500, 200, 300, 350};
        final int output = 900;
        Assertions.assertEquals(output, getMaximumGoldV2(w, n, p, g));
    }
}

1143. Longest Common Subsequence

1. recursive

2. memorized

3. dp

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // return recursive(text1, text2, 0, 0);
        
        // int[][] mem = new int[text1.length()][text2.length()];
        // for (int[] row : mem) {
        //     Arrays.fill(row, -1);
        // }
        // return memorize(text1, text2, text1.length()-1, text2.length()-1, mem);

        return dp(text1, text2);
    }

    // starting from the end
    private int recursive(String text1, String text2, int index1, int index2) {
        if (index1 < 0 || index2 < 0) {
            return 0;
        }
        if (text1.charAt(index1) == text2.charAt(index2)) {
            return 1 + recursive(text1, text2, index1-1, index2-1);
        } else {
            return Math.max(recursive(text1, text2, index1-1, index2), recursive(text1, text2, index1, index2-1));
        }
    }
    // or starting from the begining 

    private int memorize(String text1, String text2, int index1, int index2, int[][] mem) {
        if (index1 < 0 || index2 < 0) {
            return 0;
        }
        if (mem[index1][index2] != -1) {
            return mem[index1][index2];
        }
        if (text1.charAt(index1) == text2.charAt(index2)) {
            mem[index1][index2] = 1 + memorize(text1, text2, index1-1, index2-1, mem);
        } else {
            mem[index1][index2] = Math.max(memorize(text1, text2, index1-1, index2, mem), memorize(text1, text2, index1, index2-1, mem));
        }
        return mem[index1][index2];
    }

    private int dp(String text1, String text2) {
        int dp[][] = new int[text1.length()+1][text2.length()+1];
        for (int i = 1; i <= text1.length(); i++) {
            for (int j = 1; j <= text2.length(); j++) {
                if (text1.charAt(i-1) == text2.charAt(j-1)) {
                    dp[i][j] = 1 + dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

// https://leetcode.com/problems/longest-common-subsequence/solutions/5571313/java-solution-for-longest-common-subsequence-3-approaches-detailed-explanation
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        // return recursive(text1, text2, text1.length()-1, text2.length()-1);   

        // vector<vector<int>> mem(text1.length(), vector<int>(text2.length(), -1));
        // for (auto& row : mem) {
        //     std:fill(row.begin(), row.end(), -1);
        // }
        // return memorize(text1, text2, text1.length()-1, text2.length()-1, mem);

        return dp(text1, text2);
    }

    int recursive(string text1, string text2, int i, int j) {
        if (i < 0 || j < 0) {
            return 0;
        }
        if (text1[i] == text2[j]) {
            return 1 + recursive(text1, text2, i-1, j-1);
        } else {
            return max(recursive(text1, text2, i-1, j), recursive(text1, text2, i, j-1));
        }
    }

    int memorize(string text1, string text2, int i, int j, vector<vector<int>> mem) {
        if (i < 0 || j < 0) {
            return 0;
        }
        if (mem[i][j] != -1) {
            return mem[i][j];
        }
        if (text1[i] == text2[j]) {
            mem[i][j] = 1 + memorize(text1, text2, i-1, j-1, mem);
        } else {
            mem[i][j] = max(memorize(text1, text2, i-1, j, mem), memorize(text1, text2, i, j-1, mem));
        }
        return mem[i][j];
    }

    int dp(string text1, string text2) {
        int row = text1.length()+1;
        int col = text2.length()+1;
        int matrix[row][col];
        std::fill(&matrix[0][0], &matrix[0][0] + row * col, 0);
        for (int i = 1; i <= row-1; i++) {
            for (int j = 1; j <= col-1; j++) {
                // note we start from the first char (0) to the last char
                if (text1[i-1] == text2[j-1]) { 
                    matrix[i][j] = 1 + matrix[i-1][j-1];
                } else {
                    matrix[i][j] = max(matrix[i][j-1], matrix[i-1][j]);
                }
            }
        }
        return matrix[row-1][col-1];
    }
};