// Generated by scripts/make-single-file.sh from the java-interview-lab/dynamic-programming module.
// Run with: java DynamicProgrammingTenProblems.java   (JDK 25)
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/** Prints a one-line answer for each of the ten problems. Run: java DynamicProgrammingTenProblems.java */
public class DynamicProgrammingTenProblems {
    public static void main(String[] args) {
        long[] calls = {0};
        System.out.println("1  Fibonacci(40)              naive = " + Fibonacci.naive(40, calls) + " (" + calls[0] + " calls)");
        calls[0] = 0;
        System.out.println("                              memo  = " + Fibonacci.memo(40, calls) + " (" + calls[0] + " calls)");
        System.out.println("2  Climbing stairs(10)        " + ClimbingStairs.tabulation(10));
        System.out.println("3  House robber [2,7,9,3,1]   " + HouseRobber.tabulation(new int[] {2, 7, 9, 3, 1}));
        System.out.println("4  Coin change {1,3,4}, 6     " + CoinChange.tabulation(new int[] {1, 3, 4}, 6) + " coins (greedy says " + CoinChange.greedy(new int[] {1, 3, 4}, 6) + ")");
        System.out.println("5  LIS [10,9,2,5,3,7,101,18]  " + LongestIncreasingSubsequence.tabulation(new int[] {10, 9, 2, 5, 3, 7, 101, 18}));
        System.out.println("6  Knapsack 0/1               " + Knapsack01.oneRowBackward(new int[] {5, 4, 6, 3}, new int[] {10, 40, 30, 50}, 10));
        System.out.println("7  LCS ABCBDAB / BDCABA       " + Lcs.tabulation("ABCBDAB", "BDCABA"));
        System.out.println("8  Edit distance kitten/sitting " + EditDistance.tabulation("kitten", "sitting"));
        System.out.println("9  Unique paths 3 x 7         " + UniquePaths.tabulation(3, 7));
        System.out.println("10 Partition [1,5,11,5]       " + PartitionEqualSubsetSum.tabulation(new int[] {1, 5, 11, 5}));
    }
}

/**
 * Problem 1: Fibonacci. F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2).
 * The smallest problem that shows every idea in dynamic programming.
 * All results are exact: Math.addExact throws once a value no longer fits in a long (n = 93).
 */
final class Fibonacci {
    private Fibonacci() {}

    /** Plain recursion. Correct, and exponentially slow. {@code calls[0]} counts every call made. */
    public static long naive(int n, long[] calls) {
        calls[0]++;
        if (n < 2) return n;
        return Math.addExact(naive(n - 1, calls), naive(n - 2, calls));
    }

    /** Top-down: the same recursion, plus a notebook (memo) so each n is solved only once. */
    public static long memo(int n, long[] calls) {
        return memo(n, new long[n + 1], calls);
    }

    private static long memo(int n, long[] notebook, long[] calls) {
        calls[0]++;
        if (n < 2) return n;
        if (notebook[n] != 0) return notebook[n];          // 0 means "not solved yet" (F(n) > 0 for n >= 1)
        return notebook[n] = Math.addExact(memo(n - 1, notebook, calls), memo(n - 2, notebook, calls));
    }

    /** Bottom-up: fill a table from the smallest subproblem upwards. No recursion at all. */
    public static long tabulation(int n) {
        if (n < 2) return n;
        long[] dp = new long[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) dp[i] = Math.addExact(dp[i - 1], dp[i - 2]);
        return dp[n];
    }

    /** Space-optimised: dp[i] only needs the previous two cells, so keep two variables. */
    public static long twoVariables(int n) {
        if (n < 2) return n;
        long prev = 0, curr = 1;
        for (int i = 2; i <= n; i++) {
            long next = Math.addExact(prev, curr);
            prev = curr;
            curr = next;
        }
        return curr;
    }

    /**
     * The tempting one-liner memo. On JDK 9 and later HashMap.computeIfAbsent detects that the mapping
     * function changed the map and throws ConcurrentModificationException.
     */
    public static long memoWithComputeIfAbsent(int n, Map<Integer, Long> cache) {
        if (n < 2) return n;
        return cache.computeIfAbsent(n, k -> memoWithComputeIfAbsent(k - 1, cache) + memoWithComputeIfAbsent(k - 2, cache));
    }

    /** The safe version of the same idea: look up, compute, then put. */
    public static long memoWithGetAndPut(int n, Map<Integer, Long> cache) {
        if (n < 2) return n;
        Long hit = cache.get(n);
        if (hit != null) return hit;
        long value = memoWithGetAndPut(n - 1, cache) + memoWithGetAndPut(n - 2, cache);
        cache.put(n, value);
        return value;
    }

    public static Map<Integer, Long> newCache() { return new HashMap<>(); }
}

/**
 * Problem 2: Climbing Stairs. You may climb 1 or 2 steps at a time. How many distinct ways reach step n?
 * ways(n) = ways(n-1) + ways(n-2): the last move was either a 1-step or a 2-step. (It is Fibonacci in disguise.)
 */
final class ClimbingStairs {
    private ClimbingStairs() {}

    public static long memo(int n) {
        return memo(n, new long[n + 2]);
    }

    private static long memo(int n, long[] notebook) {
        if (n <= 1) return 1;                              // one way to stand still, one way to take a single step
        if (notebook[n] != 0) return notebook[n];
        return notebook[n] = memo(n - 1, notebook) + memo(n - 2, notebook);
    }

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

    public static long twoVariables(int n) {
        long prev = 1, curr = 1;
        for (int i = 2; i <= n; i++) {
            long next = prev + curr;
            prev = curr;
            curr = next;
        }
        return curr;
    }
}

/**
 * Problem 3: House Robber. Pick houses to maximise money, never two neighbours.
 * best(i) = max(best(i-1), best(i-2) + money[i]): skip house i, or take it and jump over its neighbour.
 */
final class HouseRobber {
    private HouseRobber() {}

    public static int memo(int[] money) {
        int[] notebook = new int[money.length];
        java.util.Arrays.fill(notebook, -1);               // -1 = "not solved"; 0 is a legitimate answer
        return memo(money, money.length - 1, notebook);
    }

    private static int memo(int[] money, int i, int[] notebook) {
        if (i < 0) return 0;
        if (notebook[i] != -1) return notebook[i];
        return notebook[i] = Math.max(memo(money, i - 1, notebook), memo(money, i - 2, notebook) + money[i]);
    }

    /** dp[k] = best total using only the first k houses. dp[0] = 0 (no houses). */
    public static int[] table(int[] money) {
        int[] dp = new int[money.length + 1];
        for (int k = 1; k <= money.length; k++) {
            int skip = dp[k - 1];
            int take = (k >= 2 ? dp[k - 2] : 0) + money[k - 1];
            dp[k] = Math.max(skip, take);
        }
        return dp;
    }

    public static int tabulation(int[] money) {
        return table(money)[money.length];
    }

    public static int twoVariables(int[] money) {
        int prev2 = 0, prev1 = 0;                          // best up to two houses ago, best up to the previous house
        for (int m : money) {
            int best = Math.max(prev1, prev2 + m);
            prev2 = prev1;
            prev1 = best;
        }
        return prev1;
    }
}

/**
 * Problem 4: Coin Change. Fewest coins that add up to an amount (unlimited supply of each coin), or -1 if impossible.
 * fewest(a) = 1 + min over coins c of fewest(a - c).
 * Also: how many ways can the coins make the amount, and why the loop order of that table matters.
 */
final class CoinChange {
    private CoinChange() {}

    /** Greedy "always take the biggest coin". Wrong for some coin systems, e.g. {1,3,4} and amount 6. */
    public static int greedy(int[] coins, int amount) {
        int[] sorted = coins.clone();
        Arrays.sort(sorted);
        int count = 0;
        for (int i = sorted.length - 1; i >= 0 && amount > 0; i--) {
            count += amount / sorted[i];
            amount %= sorted[i];
        }
        return amount == 0 ? count : -1;
    }

    /** Plain recursion; {@code calls[0]} counts the calls. Exponential. */
    public static int naive(int[] coins, int amount, long[] calls) {
        calls[0]++;
        if (amount == 0) return 0;
        int best = -1;
        for (int c : coins) {
            if (c > amount) continue;
            int sub = naive(coins, amount - c, calls);
            if (sub >= 0 && (best == -1 || sub + 1 < best)) best = sub + 1;
        }
        return best;
    }

    /** Top-down with a notebook. -2 = "not solved", -1 = "solved: impossible". */
    public static int memo(int[] coins, int amount, long[] calls) {
        int[] notebook = new int[amount + 1];
        Arrays.fill(notebook, -2);
        return memo(coins, amount, notebook, calls);
    }

    private static int memo(int[] coins, int amount, int[] notebook, long[] calls) {
        calls[0]++;
        if (amount == 0) return 0;
        if (notebook[amount] != -2) return notebook[amount];
        int best = -1;
        for (int c : coins) {
            if (c > amount) continue;
            int sub = memo(coins, amount - c, notebook, calls);
            if (sub >= 0 && (best == -1 || sub + 1 < best)) best = sub + 1;
        }
        return notebook[amount] = best;
    }

    /** Bottom-up. "Impossible" is amount + 1, a value that can never be a real answer, so adding 1 cannot overflow. */
    public static int tabulation(int[] coins, int amount) {
        int impossible = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, impossible);
        dp[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
            }
        }
        return dp[amount] >= impossible ? -1 : dp[amount];
    }

    /** The classic bug: Integer.MAX_VALUE as "impossible", then dp[a - c] + 1 wraps around to a negative number. */
    public static int tabulationOverflowBug(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }

    /** Number of COMBINATIONS (order ignored): coins in the OUTER loop. 1D array, which is already the space-optimised form. */
    public static long countCombinations(int[] coins, int amount) {
        long[] ways = new long[amount + 1];
        ways[0] = 1;
        for (int c : coins) {
            for (int a = c; a <= amount; a++) ways[a] += ways[a - c];
        }
        return ways[amount];
    }

    /** Swap the loops (amount outer) and the same table now counts PERMUTATIONS (order matters): a different problem. */
    public static long countPermutations(int[] coins, int amount) {
        long[] ways = new long[amount + 1];
        ways[0] = 1;
        for (int a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a) ways[a] += ways[a - c];
            }
        }
        return ways[amount];
    }
}

/**
 * Problem 5: Longest Increasing Subsequence (strictly increasing, elements need not be adjacent).
 * endingAt(i) = 1 + max endingAt(j) over j < i with a[j] < a[i]. The answer is the maximum over all i.
 */
final class LongestIncreasingSubsequence {
    private LongestIncreasingSubsequence() {}

    public static int memo(int[] a) {
        int[] notebook = new int[a.length];                // 0 = not solved (a real answer is at least 1)
        int best = 0;
        for (int i = 0; i < a.length; i++) best = Math.max(best, endingAt(a, i, notebook));
        return best;
    }

    private static int endingAt(int[] a, int i, int[] notebook) {
        if (notebook[i] != 0) return notebook[i];
        int best = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) best = Math.max(best, 1 + endingAt(a, j, notebook));
        }
        return notebook[i] = best;
    }

    /** O(n^2) table: dp[i] = length of the best increasing subsequence that ENDS at index i. */
    public static int[] table(int[] a) {
        int[] dp = new int[a.length];
        Arrays.fill(dp, 1);
        for (int i = 1; i < a.length; i++) {
            for (int j = 0; j < i; j++) {
                if (a[j] < a[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        return dp;
    }

    public static int tabulation(int[] a) {
        return Arrays.stream(table(a)).max().orElse(0);
    }

    /**
     * O(n log n) "patience" version: tails[k] = the smallest possible last value of an increasing subsequence of length k+1.
     * Not a table of subproblems any more, but the interviewer's usual follow-up.
     */
    public static int patience(int[] a) {
        int[] tails = new int[a.length];
        int size = 0;
        for (int x : a) {
            int pos = Arrays.binarySearch(tails, 0, size, x);
            if (pos < 0) pos = -(pos + 1);                 // first tail >= x
            tails[pos] = x;
            if (pos == size) size++;
        }
        return size;
    }
}

/**
 * Problem 6: 0/1 Knapsack. Each item may be taken at most once. Maximise total value within a weight capacity.
 * best(i, w) = max(best(i-1, w), value[i] + best(i-1, w - weight[i])): leave item i, or take it.
 */
final class Knapsack01 {
    private Knapsack01() {}

    public static int naive(int[] weight, int[] value, int capacity, long[] calls) {
        return naive(weight, value, weight.length - 1, capacity, calls);
    }

    private static int naive(int[] weight, int[] value, int i, int cap, long[] calls) {
        calls[0]++;
        if (i < 0) return 0;
        int leave = naive(weight, value, i - 1, cap, calls);
        if (weight[i] > cap) return leave;
        return Math.max(leave, value[i] + naive(weight, value, i - 1, cap - weight[i], calls));
    }

    /** Top-down: the state is TWO numbers (item index, remaining capacity), so the notebook is 2-D. */
    public static int memo(int[] weight, int[] value, int capacity, long[] calls) {
        int[][] notebook = new int[weight.length][capacity + 1];
        for (int[] row : notebook) Arrays.fill(row, -1);
        return memo(weight, value, weight.length - 1, capacity, notebook, calls);
    }

    private static int memo(int[] weight, int[] value, int i, int cap, int[][] notebook, long[] calls) {
        calls[0]++;
        if (i < 0) return 0;
        if (notebook[i][cap] != -1) return notebook[i][cap];
        int leave = memo(weight, value, i - 1, cap, notebook, calls);
        int best = leave;
        if (weight[i] <= cap) best = Math.max(leave, value[i] + memo(weight, value, i - 1, cap - weight[i], notebook, calls));
        return notebook[i][cap] = best;
    }

    /** dp[i][w] = best value using only the first i items with capacity w. */
    public static int[][] table(int[] weight, int[] value, int capacity) {
        int n = weight.length;
        int[][] dp = new int[n + 1][capacity + 1];
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                dp[i][w] = dp[i - 1][w];
                if (weight[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i][w], value[i - 1] + dp[i - 1][w - weight[i - 1]]);
                }
            }
        }
        return dp;
    }

    public static int tabulation(int[] weight, int[] value, int capacity) {
        return table(weight, value, capacity)[weight.length][capacity];
    }

    /** One row is enough, but the capacity loop MUST run downwards so each item is used at most once. */
    public static int oneRowBackward(int[] weight, int[] value, int capacity) {
        int[] dp = new int[capacity + 1];
        for (int i = 0; i < weight.length; i++) {
            for (int w = capacity; w >= weight[i]; w--) {
                dp[w] = Math.max(dp[w], value[i] + dp[w - weight[i]]);
            }
        }
        return dp[capacity];
    }

    /** Same code with the loop flipped. It compiles, runs, and silently answers a different problem (unbounded knapsack). */
    public static int oneRowForwardBug(int[] weight, int[] value, int capacity) {
        int[] dp = new int[capacity + 1];
        for (int i = 0; i < weight.length; i++) {
            for (int w = weight[i]; w <= capacity; w++) {
                dp[w] = Math.max(dp[w], value[i] + dp[w - weight[i]]);
            }
        }
        return dp[capacity];
    }
}

/**
 * Problem 7: Longest Common Subsequence of two strings (characters in order, not necessarily adjacent).
 * lcs(i, j) = a[i-1]==b[j-1] ? 1 + lcs(i-1, j-1) : max(lcs(i-1, j), lcs(i, j-1)).
 */
final class Lcs {
    private Lcs() {}

    public static int naive(String a, String b, long[] calls) {
        return naive(a, b, a.length(), b.length(), calls);
    }

    private static int naive(String a, String b, int i, int j, long[] calls) {
        calls[0]++;
        if (i == 0 || j == 0) return 0;
        if (a.charAt(i - 1) == b.charAt(j - 1)) return 1 + naive(a, b, i - 1, j - 1, calls);
        return Math.max(naive(a, b, i - 1, j, calls), naive(a, b, i, j - 1, calls));
    }

    public static int memo(String a, String b, long[] calls) {
        int[][] notebook = new int[a.length() + 1][b.length() + 1];
        for (int[] row : notebook) Arrays.fill(row, -1);
        return memo(a, b, a.length(), b.length(), notebook, calls);
    }

    private static int memo(String a, String b, int i, int j, int[][] notebook, long[] calls) {
        calls[0]++;
        if (i == 0 || j == 0) return 0;
        if (notebook[i][j] != -1) return notebook[i][j];
        int result = a.charAt(i - 1) == b.charAt(j - 1)
                ? 1 + memo(a, b, i - 1, j - 1, notebook, calls)
                : Math.max(memo(a, b, i - 1, j, notebook, calls), memo(a, b, i, j - 1, notebook, calls));
        return notebook[i][j] = result;
    }

    /** dp[i][j] = LCS length of the first i characters of a and the first j characters of b. */
    public static int[][] table(String a, String b) {
        int[][] dp = new int[a.length() + 1][b.length() + 1];
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
                        ? dp[i - 1][j - 1] + 1
                        : Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp;
    }

    public static int tabulation(String a, String b) {
        return table(a, b)[a.length()][b.length()];
    }

    /** Walk the full table backwards from the corner to recover an actual subsequence. Needs the whole table. */
    public static String reconstruct(String a, String b, int[][] dp) {
        StringBuilder sb = new StringBuilder();
        int i = a.length(), j = b.length();
        while (i > 0 && j > 0) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                sb.append(a.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] >= dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        return sb.reverse().toString();
    }

    /** Two rows instead of the full table: O(min-length) memory, but the answer is a length only; no reconstruction. */
    public static int twoRows(String a, String b) {
        int[] prev = new int[b.length() + 1];
        int[] curr = new int[b.length() + 1];
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                curr[j] = a.charAt(i - 1) == b.charAt(j - 1)
                        ? prev[j - 1] + 1
                        : Math.max(prev[j], curr[j - 1]);
            }
            int[] tmp = prev; prev = curr; curr = tmp;
        }
        return prev[b.length()];
    }
}

/**
 * Problem 8: Edit Distance (Levenshtein). Fewest insert / delete / replace operations that turn a into b.
 * dist(i, j) = a[i-1]==b[j-1] ? dist(i-1, j-1) : 1 + min(dist(i-1, j) [delete], dist(i, j-1) [insert], dist(i-1, j-1) [replace]).
 */
final class EditDistance {
    private EditDistance() {}

    public static int memo(String a, String b) {
        int[][] notebook = new int[a.length() + 1][b.length() + 1];
        for (int[] row : notebook) Arrays.fill(row, -1);
        return memo(a, b, a.length(), b.length(), notebook);
    }

    private static int memo(String a, String b, int i, int j, int[][] notebook) {
        if (i == 0) return j;                              // only inserts left
        if (j == 0) return i;                              // only deletes left
        if (notebook[i][j] != -1) return notebook[i][j];
        int result;
        if (a.charAt(i - 1) == b.charAt(j - 1)) {
            result = memo(a, b, i - 1, j - 1, notebook);
        } else {
            result = 1 + Math.min(memo(a, b, i - 1, j, notebook),
                    Math.min(memo(a, b, i, j - 1, notebook), memo(a, b, i - 1, j - 1, notebook)));
        }
        return notebook[i][j] = result;
    }

    public static int[][] table(String a, String b) {
        int[][] dp = new int[a.length() + 1][b.length() + 1];
        for (int i = 0; i <= a.length(); i++) dp[i][0] = i;
        for (int j = 0; j <= b.length(); j++) dp[0][j] = j;
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
                        ? dp[i - 1][j - 1]
                        : 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
            }
        }
        return dp;
    }

    public static int tabulation(String a, String b) {
        return table(a, b)[a.length()][b.length()];
    }

    public static int twoRows(String a, String b) {
        int[] prev = new int[b.length() + 1];
        int[] curr = new int[b.length() + 1];
        for (int j = 0; j <= b.length(); j++) prev[j] = j;
        for (int i = 1; i <= a.length(); i++) {
            curr[0] = i;
            for (int j = 1; j <= b.length(); j++) {
                curr[j] = a.charAt(i - 1) == b.charAt(j - 1)
                        ? prev[j - 1]
                        : 1 + Math.min(prev[j], Math.min(curr[j - 1], prev[j - 1]));
            }
            int[] tmp = prev; prev = curr; curr = tmp;
        }
        return prev[b.length()];
    }
}

/**
 * Problem 9: Unique Paths. A robot on an m x n grid starts top-left and may only move right or down.
 * How many routes reach the bottom-right? paths(r, c) = paths(r-1, c) + paths(r, c-1).
 */
final class UniquePaths {
    private UniquePaths() {}

    public static long memo(int rows, int cols) {
        return memo(rows - 1, cols - 1, new long[rows][cols]);
    }

    private static long memo(int r, int c, long[][] notebook) {
        if (r == 0 || c == 0) return 1;                    // one straight line along an edge
        if (notebook[r][c] != 0) return notebook[r][c];
        return notebook[r][c] = memo(r - 1, c, notebook) + memo(r, c - 1, notebook);
    }

    public static long[][] table(int rows, int cols) {
        long[][] dp = new long[rows][cols];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                dp[r][c] = (r == 0 || c == 0) ? 1 : dp[r - 1][c] + dp[r][c - 1];
            }
        }
        return dp;
    }

    public static long tabulation(int rows, int cols) {
        return table(rows, cols)[rows - 1][cols - 1];
    }

    /** One row: row[c] already holds the cell above, row[c-1] is the cell to the left. */
    public static long oneRow(int rows, int cols) {
        long[] row = new long[cols];
        java.util.Arrays.fill(row, 1);
        for (int r = 1; r < rows; r++) {
            for (int c = 1; c < cols; c++) row[c] += row[c - 1];
        }
        return row[cols - 1];
    }

    /** Closed form check: choose which (rows-1) of the (rows+cols-2) moves are "down". */
    public static long binomial(int rows, int cols) {
        long result = 1;
        int k = Math.min(rows - 1, cols - 1), n = rows + cols - 2;
        for (int i = 1; i <= k; i++) result = result * (n - k + i) / i;   // stays an exact integer at every step
        return result;
    }
}

/**
 * Problem 10: Partition Equal Subset Sum. Can the numbers be split into two groups with the same sum?
 * Equivalent question: can some subset reach exactly total/2? (A yes/no knapsack with no values.)
 */
final class PartitionEqualSubsetSum {
    private PartitionEqualSubsetSum() {}

    public static boolean memo(int[] nums) {
        int total = Arrays.stream(nums).sum();
        if (total % 2 != 0) return false;                  // an odd total can never split evenly
        int target = total / 2;
        Boolean[][] notebook = new Boolean[nums.length][target + 1];
        return memo(nums, nums.length - 1, target, notebook);
    }

    private static boolean memo(int[] nums, int i, int remaining, Boolean[][] notebook) {
        if (remaining == 0) return true;
        if (i < 0 || remaining < 0) return false;
        if (notebook[i][remaining] != null) return notebook[i][remaining];
        boolean result = memo(nums, i - 1, remaining - nums[i], notebook) || memo(nums, i - 1, remaining, notebook);
        return notebook[i][remaining] = result;
    }

    /** dp[i][s] = can the first i numbers make sum s? */
    public static boolean[][] table(int[] nums, int target) {
        boolean[][] dp = new boolean[nums.length + 1][target + 1];
        dp[0][0] = true;
        for (int i = 1; i <= nums.length; i++) {
            for (int s = 0; s <= target; s++) {
                dp[i][s] = dp[i - 1][s] || (s >= nums[i - 1] && dp[i - 1][s - nums[i - 1]]);
            }
        }
        return dp;
    }

    public static boolean tabulation(int[] nums) {
        int total = Arrays.stream(nums).sum();
        if (total % 2 != 0) return false;
        return table(nums, total / 2)[nums.length][total / 2];
    }

    /** One boolean row; sums run downwards for the same reason as 0/1 knapsack. */
    public static boolean oneRow(int[] nums) {
        int total = Arrays.stream(nums).sum();
        if (total % 2 != 0) return false;
        int target = total / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int x : nums) {
            for (int s = target; s >= x; s--) dp[s] = dp[s] || dp[s - x];
        }
        return dp[target];
    }
}