Dynamic Programming

import java.util.Arrays;

public class Knapsack {

    // Memoization (Top-Down) — O(n*W) time and space
    static int[][] memo;

    static int knapsackMemo(int[] wt, int[] val, int W, int n) {
        if (n == 0 || W == 0) return 0;
        if (memo[n][W] != -1) return memo[n][W];

        if (wt[n - 1] > W) {
            // Item too heavy — skip it
            memo[n][W] = knapsackMemo(wt, val, W, n - 1);
        } else {
            // Max of: skip item OR take item
            memo[n][W] = Math.max(
                knapsackMemo(wt, val, W, n - 1),
                val[n - 1] + knapsackMemo(wt, val, W - wt[n - 1], n - 1)
            );
        }
        return memo[n][W];
    }

    // Tabulation (Bottom-Up) — O(n*W) time and space
    static int knapsackDP(int[] wt, int[] val, int W) {
        int n = wt.length;
        int[][] dp = new int[n + 1][W + 1];

        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                dp[i][w] = dp[i - 1][w];  // don't take item i
                if (wt[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i][w],
                        val[i - 1] + dp[i - 1][w - wt[i - 1]]);  // take item i
                }
            }
        }
        return dp[n][W];
    }

    public static void main(String[] args) {
        int[] weights = {1, 3, 4, 5};
        int[] values  = {1, 4, 5, 7};
        int capacity  = 7;
        int n = weights.length;

        memo = new int[n + 1][capacity + 1];
        for (int[] row : memo) Arrays.fill(row, -1);

        System.out.println("Memo: " + knapsackMemo(weights, values, capacity, n));  // 9
        System.out.println("DP:   " + knapsackDP(weights, values, capacity));       // 9
    }
}

/*
 * For capacity=7, items={(w=1,v=1),(w=3,v=4),(w=4,v=5),(w=5,v=7)}:
 * Optimal: take items (w=3,v=4) + (w=4,v=5) = weight 7, value 9
 */

public class LCS {

    // LCS length — O(m*n) time and space
    static int lcs(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];  // characters match
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);  // take max
                }
            }
        }
        return dp[m][n];
    }

    // Reconstruct the actual LCS string
    static String lcsString(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = (s1.charAt(i-1) == s2.charAt(j-1))
                    ? 1 + dp[i-1][j-1]
                    : Math.max(dp[i-1][j], dp[i][j-1]);

        // Backtrack to find the LCS
        StringBuilder sb = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                sb.append(s1.charAt(i-1));
                i--; j--;
            } else if (dp[i-1][j] > dp[i][j-1]) i--;
            else j--;
        }
        return sb.reverse().toString();
    }

    public static void main(String[] args) {
        System.out.println(lcs("ABCBDAB", "BDCAB"));       // 4
        System.out.println(lcsString("ABCBDAB", "BDCAB")); // BCAB or BDAB
    }
}

import java.util.Arrays;

public class CoinChangeDP {

    // Minimum coins to make 'amount' — O(n * amount) time and space
    static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);  // initialize with "infinity"
        dp[0] = 0;  // base case: 0 coins needed for amount 0

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins1 = {1, 5, 6, 9};
        System.out.println("Coins {1,5,6,9}, amount=11: " + coinChange(coins1, 11));
        // Answer: 2 (coins 5+6=11) — greedy would give 3 (9+1+1)

        int[] coins2 = {1, 2, 5};
        System.out.println("Coins {1,2,5}, amount=11: " + coinChange(coins2, 11));
        // Answer: 3 (5+5+1=11)

        int[] coins3 = {2};
        System.out.println("Coins {2}, amount=3: " + coinChange(coins3, 3));
        // Answer: -1 (impossible)
    }
}

/*
 * DP Table trace for coins={1,5,6,9}, amount=11:
 * dp[0]=0
 * dp[1]=1  (1)
 * dp[2]=2  (1+1)
 * dp[3]=3  (1+1+1)
 * dp[4]=4  (1+1+1+1)
 * dp[5]=1  (5)
 * dp[6]=1  (6)
 * dp[7]=2  (1+6 or 1+6)
 * dp[8]=2  (2+6 — wait, no 2 coin. 1+1+6=3? No: dp[8]=min(dp[7]+1, dp[3]+1)=min(3,4)=3)
 * dp[9]=1  (9)
 * dp[10]=2 (1+9)
 * dp[11]=2 (5+6) ← optimal!
 */