DP — 實戰題解

# python
# LC 343 - Integer Break
# IDEA: dp[i] = best product of >= 2 parts summing to i; for each split, keep the rest whole or split it
# time = O(n^2), space = O(n)
def integerBreak(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        for j in range(1, i):            # the first part is j
            keep_rest = j * (i - j)      # stop: i - j stays one part
            break_rest = j * dp[i - j]   # split i - j further
            dp[i] = max(dp[i], keep_rest, break_rest)
    return dp[n]

// java
// LC 343 - Integer Break
// IDEA: dp[i] = best product of >= 2 parts summing to i; for each split, keep the rest whole or split it
// time = O(n^2), space = O(n)
public int integerBreak(int n) {
    int[] dp = new int[n + 1];
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            int keepRest = j * (i - j);          // stop splitting: i - j stays whole
            int breakRest = j * dp[i - j];       // split i - j further
            dp[i] = Math.max(dp[i], Math.max(keepRest, breakRest));
        }
    }
    return dp[n];
}

i      1  2  3  4  5  6  7   8   9   10
dp[i]  1  1  2  4  6  9  12  18  27  36

# python
# LC 91 - Decode Ways
# IDEA: dp[i] = ways to decode s[:i]; one-digit step if s[i-1] != '0', two-digit step if 10..26
# time = O(n), space = O(n)
def numDecodings(s):
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1                            # the empty prefix decodes one way
    for i in range(1, n + 1):
        if s[i - 1] != "0":              # s[i-1] alone is a letter
            dp[i] += dp[i - 1]
        if i >= 2 and 10 <= int(s[i - 2:i]) <= 26:   # s[i-2:i] together is a letter
            dp[i] += dp[i - 2]
    return dp[n]

// java
// LC 91 - Decode Ways
// IDEA: dp[i] = ways to decode s[:i]; one-digit step if s[i-1] != '0', two-digit step if 10..26
// time = O(n), space = O(n)
public int numDecodings(String s) {
    int n = s.length();
    int[] dp = new int[n + 1];
    dp[0] = 1;                                   // the empty prefix: one way
    for (int i = 1; i <= n; i++) {
        if (s.charAt(i - 1) != '0') {            // s[i-1] decoded on its own
            dp[i] += dp[i - 1];
        }
        if (i >= 2) {
            int twoDigits = Integer.parseInt(s.substring(i - 2, i));
            if (twoDigits >= 10 && twoDigits <= 26) {   // s[i-2..i-1] decoded as a pair
                dp[i] += dp[i - 2];
            }
        }
    }
    return dp[n];
}

# python
# LC 62 - Unique Paths
# IDEA: dp[r][c] = dp[r-1][c] + dp[r][c-1]; the first row and column are 1
# time = O(m * n), space = O(m * n)
def uniquePaths(m, n):
    dp = [[1] * n for _ in range(m)]     # row 0 and column 0 stay 1
    for row in range(1, m):
        for col in range(1, n):
            dp[row][col] = dp[row - 1][col] + dp[row][col - 1]
    return dp[m - 1][n - 1]

// java
// LC 62 - Unique Paths
// IDEA: dp[r][c] = dp[r-1][c] + dp[r][c-1]; the first row and column are 1
// time = O(m * n), space = O(m * n)
public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int row = 0; row < m; row++) {
        dp[row][0] = 1;                          // first column: only straight down
    }
    for (int col = 0; col < n; col++) {
        dp[0][col] = 1;                          // first row: only straight right
    }
    for (int row = 1; row < m; row++) {
        for (int col = 1; col < n; col++) {
            dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
        }
    }
    return dp[m - 1][n - 1];
}

# python
# LC 279 - Perfect Squares
# IDEA: unbounded knapsack, min count: squares are the coins, n is the amount
# time = O(n * sqrt(n)), space = O(n)
def numSquares(n):
    dp = [0] + [n] * n                   # dp[a] = fewest squares summing to a; n ones is the worst
    for amount in range(1, n + 1):
        root = 1
        while root * root <= amount:     # every square that fits
            dp[amount] = min(dp[amount], dp[amount - root * root] + 1)
            root += 1
    return dp[n]

// java
// LC 279 - Perfect Squares
// IDEA: unbounded knapsack, min count: squares are the coins, n is the amount
// time = O(n * sqrt(n)), space = O(n)
public int numSquares(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, n);                          // n ones always works
    dp[0] = 0;
    for (int amount = 1; amount <= n; amount++) {
        for (int root = 1; root * root <= amount; root++) {
            dp[amount] = Math.min(dp[amount], dp[amount - root * root] + 1);
        }
    }
    return dp[n];
}

# python
# LC 276 - Paint Fence
# IDEA: same = ways the last post repeats its neighbour, diff = ways it does not; roll both forward
# time = O(n), space = O(1)
def numWays(n, k):
    if n == 0:
        return 0
    if n == 1:
        return k
    same = k                             # posts 1-2 the same colour
    diff = k * (k - 1)                   # posts 1-2 different
    for _ in range(3, n + 1):
        prev_same = same
        same = diff                      # repeat a colour only right after a change
        diff = (prev_same + diff) * (k - 1)   # any of the other k - 1 colours
    return same + diff

// java
// LC 276 - Paint Fence
// IDEA: same = ways the last post repeats its neighbour, diff = ways it does not; roll both forward
// time = O(n), space = O(1)
public int numWays(int n, int k) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return k;
    }
    int same = k;                                // posts 1-2 the same colour
    int diff = k * (k - 1);                      // posts 1-2 different
    for (int i = 3; i <= n; i++) {
        int prevSame = same;
        same = diff;                             // repeat a colour only after a change
        diff = (prevSame + diff) * (k - 1);      // any of the other k - 1 colours
    }
    return same + diff;
}

# python
# LC 1137 - N-th Tribonacci Number
# IDEA: T(n) = T(n-1) + T(n-2) + T(n-3); keep only the last three values
# time = O(n), space = O(1)
def tribonacci(n):
    if n == 0:
        return 0
    if n <= 2:
        return 1
    a, b, c = 0, 1, 1                    # T(i-3), T(i-2), T(i-1)
    for _ in range(3, n + 1):
        nxt = a + b + c
        a = b                            # shift oldest first
        b = c
        c = nxt
    return c

// java
// LC 1137 - N-th Tribonacci Number
// IDEA: T(n) = T(n-1) + T(n-2) + T(n-3); keep only the last three values
// time = O(n), space = O(1)
public int tribonacci(int n) {
    if (n == 0) {
        return 0;
    }
    if (n <= 2) {
        return 1;
    }
    int a = 0, b = 1, c = 1;                     // T(i-3), T(i-2), T(i-1)
    for (int i = 3; i <= n; i++) {
        int next = a + b + c;
        a = b;                                   // shift oldest first
        b = c;
        c = next;
    }
    return c;
}