Feb 4, 2025

Dynamic Programming - 1D

Overview

Dynamic programming stores the answers to overlapping subproblems so they are computed only once. “1D” describes the state, not necessarily the input: one index may represent a prefix length, array position, day, numeric value, subsequence length, or a job in sorted order.

The most important step is to define the exact scope of a state. For example, dp[i] might mean the best answer among the first i items, the number of ways to build a prefix of length i, or the best subarray that must end at i. These definitions lead to different transitions and return values.

Common 1D DP patterns include:

Fixed look-back: derive dp[i] from a constant number of earlier states such as dp[i - 1], dp[i - 2], and dp[i - 3].
Ending at the current position: track the best result that must include the current value, plus a separate global result. Kadane’s algorithm follows this pattern.
State machine: keep several meanings for each step, such as bought, sold, and rest. Compute every new state from the previous step’s states.
Sorted predecessor: sort the input and use binary search to find the earlier compatible state, as in weighted job scheduling.
Compressed representative state: store only the best representative for each length or category, such as the smallest ending value for each increasing-subsequence length.

Write the base cases before the loop and iterate only after every dependency is available. A table is usually O(n) space; if each state depends on only a fixed number of previous states, it can often be compressed to O(1). Keep the table when later transitions need nonlocal entries or when the actual choices must be reconstructed. Also check whether the recurrence has a direct mathematical form—the vowel-string counting problem, for example, can be reduced to a combinatorics formula.

Templates

Define dp[i] as the maximum sum obtainable from the first i values without choosing adjacent values.
Use dp[0] = 0; for one value, either skip it or take it.
At position i, compare skip = dp[i - 1] with take = dp[i - 2] + values[i - 1].
Store dp[i] = max(skip, take) and return dp[n].
Once the table version is correct, it may be compressed because the transition uses only two previous states.

class OneDimensionalDpTemplate {
    public int maxNonAdjacentSum(int[] values) {
        int N = values.length;
        if (N == 0) {
            return 0;
        }

        int[] dp = new int[N + 1];
        dp[1] = Math.max(0, values[0]);

        for (int i = 2; i <= N; i++) {
            int skip = dp[i - 1];
            int take = dp[i - 2] + values[i - 1];
            dp[i] = Math.max(skip, take);
        }

        return dp[N];
    }
}

def max_non_adjacent_sum(values: list[int]) -> int:
    N = len(values)
    if N == 0:
        return 0

    dp = [0] * (N + 1)
    dp[1] = max(0, values[0])

    for i in range(2, N + 1):
        skip = dp[i - 1]
        take = dp[i - 2] + values[i - 1]
        dp[i] = max(skip, take)

    return dp[N]

Problems

338. Counting Bits

Compute the number of set bits for every integer from 0 through n. Removing the last binary bit gives x // 2, whose answer is already known, while x % 2 tells whether the removed bit contributes one.

class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int x = 1; x <= n; x++) {
            // x / 2 is x >> 1 and x % 2 is x & 1
            res[x] = res[x / 2] + x % 2;
        }
        return res;
    }
}

from typing import List

class Solution:
    def countBits(self, n: int) -> List[int]:
        res = [0] * (n + 1)
        for x in range(1, n + 1):
            # x // 2 is x >> 1 and x % 2 is x & 1
            res[x] = res[x // 2] + x % 2
        return res

198. House Robber

Maximize money without choosing adjacent houses. At each house, either keep the best answer through the previous house or rob the current house and add it to the answer from two houses back.

class Solution {
    public int rob(int[] nums) {
        // dp[i]: max money we can get when we are at the ith house
        // dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])
        int N = nums.length;
        if (N == 1) {
            return nums[0];
        }

        int[] dp = new int[N];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < N; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
        }

        return dp[N - 1];
    }
}

from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        # dp[i]: max money we can get when we are at the ith house
        # dp[i] = max(dp[i-1], nums[i]+dp[i-2])
        N = len(nums)
        if N == 1:
            return nums[0]

        dp = [0] * N
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])

        for i in range(2, N):
            dp[i] = max(dp[i-1], nums[i] + dp[i-2])

        return dp[-1]

91. Decode Ways

Count valid mappings of a digit string to letters 1 through 26. A nonzero single digit extends every decoding ending one position earlier; a valid two-digit number extends those ending two positions earlier.

class Solution {
    public int numDecodings(String s) {
        int N = s.length();
        if (N == 0 || s.charAt(0) == '0') {
            return 0;
        }

        int[] dp = new int[N + 1];
        dp[0] = 1; // should be 1, not zero!
        dp[1] = 1;

        for (int i = 2; i <= N; i++) {
            if (!s.substring(i - 1, i).equals("0")) {
                dp[i] += dp[i - 1];
            }
            int pair = Integer.parseInt(s.substring(i - 2, i));
            if (9 < pair && pair < 27) {
                dp[i] += dp[i - 2];
            }
            if (dp[i] == 0) {
                return 0;
            }
        }

        return dp[N];
    }
}

class Solution:
    def numDecodings(self, s: str) -> int:
        N = len(s)
        if N == 0 or s[0] == '0':
            return 0

        dp = [0] * (1 + N)
        dp[0] = 1 # should be 1, not zero!
        dp[1] = 1

        for i in range(2, 1+N):
            if s[i-1:i] != '0':
                dp[i] += dp[i-1]
            if 9 < int(s[i-2:i]) < 27:
                dp[i] += dp[i-2]
            if dp[i] == 0:
                return 0

        return dp[-1]

300. Longest Increasing Subsequence

Maintain res[i - 1] as the smallest possible ending value of an increasing subsequence of length i. For each number, use lower-bound binary search to replace the first ending value greater than or equal to it, or append it when it extends the longest subsequence. The length of res is the answer, giving O(n log n) time.

class Solution {
    public int lengthOfLIS(int[] nums) {
        // res[i - 1]: smallest possible ending value of an increasing subsequence of length i
        int[] res = new int[nums.length];
        res[0] = nums[0];
        int size = 1;

        for (int i = 1; i < nums.length; i++) {
            int left = 0;
            int right = size;
            while (left < right) {
                int mid = (left + right) / 2;
                if (res[mid] < nums[i]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            int idx = left;
            if (idx == size) {
                size++;
            }
            res[idx] = nums[i];
        }

        return size;
    }
}

from bisect import bisect_left
from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # res[i - 1]: smallest possible ending value of an increasing subsequence of length i
        res = [nums[0]]

        for i in range(1, len(nums)):
            idx = bisect_left(res, nums[i])
            if idx == len(res):
                res.append(nums[i])
            else:
                res[idx] = nums[i]

        return len(res)

309. Best Time to Buy and Sell Stock with Cooldown

Track the best profit after each day in three states: holding a stock, having just sold, or resting without stock. A purchase can follow only a rest state, which enforces the one-day cooldown.

class Solution {
    public int maxProfit(int[] prices) {
        // Three states: sold, rest, bought.
        // Memory hook: sell, buy, rest is the best update order.
        int sold = 0;
        int bought = Integer.MIN_VALUE;
        int rest = 0;

        for (int p : prices) {
            int prevSold = sold;
            sold = bought + p;
            bought = Math.max(bought, rest - p);
            rest = Math.max(rest, prevSold);
        }

        return Math.max(rest, sold);
    }
}

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # three states: sold, rest, bought
        # sold: max profit if we sold today
        # rest: max profit if we have no stock and do nothing today
        # bought: max profit if we bought today or holds a tock today
        # for each new day, we transition these states
        # This is not greedy. It is DP because it keeps the best profit
        # for all possible meaningful states each day. Can formally prove using induction.
        # Memory hook: sell buy rest, this order is the best
        sold, bought, rest = 0, float('-inf'), 0
        for p in prices:
            prev_sold = sold
            sold = bought + p
            bought = max(bought, rest - p)
            rest = max(rest, prev_sold)

        return max(rest, sold)

918. Maximum Sum Circular Subarray

The maximum circular subarray is either an ordinary maximum subarray or a wrapped subarray. Kadane’s algorithm finds the ordinary maximum, while subtracting the minimum subarray from the total sum gives the wrapped maximum. When every number is negative, use the ordinary maximum to avoid choosing an empty subarray.

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int N = nums.length;
        int currMax = nums[0];
        int maxSum = nums[0];
        int currMin = nums[0];
        int minSum = nums[0];

        for (int i = 1; i < N; i++) {
            currMax = Math.max(nums[i], currMax + nums[i]);
            maxSum = Math.max(maxSum, currMax);
            currMin = Math.min(nums[i], currMin + nums[i]);
            minSum = Math.min(minSum, currMin);
        }

        // Condition for all negative numbers
        if (maxSum < 0) {
            return maxSum;
        }

        int total = 0;
        for (int num : nums) {
            total += num;
        }
        return Math.max(maxSum, total - minSum);
    }
}

from typing import List

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        N = len(nums)
        curr_max, max_sum = nums[0], nums[0]
        curr_min, min_sum = nums[0], nums[0]

        for i in range(1, N):
            curr_max = max(nums[i], curr_max + nums[i])
            max_sum = max(max_sum, curr_max)
            curr_min = min(nums[i], curr_min + nums[i])
            min_sum = min(min_sum, curr_min)

        # Condition for all negative numbers
        if max_sum < 0:
            return max_sum

        return max(max_sum, sum(nums)-min_sum)

1235. Maximum Profit in Job Scheduling

Sort the jobs by end time and let dp[i] be the maximum profit available after considering the first i jobs. For each job, either skip it or take it and use upper-bound binary search to count the jobs that ended no later than its start time. This weighted interval scheduling approach runs in O(n log n) time.

import java.util.Arrays;

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int N = startTime.length;
        int[][] jobs = new int[N][3];
        for (int i = 0; i < N; i++) {
            jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        }
        Arrays.sort(jobs, (a, b) -> Integer.compare(a[1], b[1]));

        int[] endTimes = new int[N];
        for (int i = 0; i < N; i++) {
            endTimes[i] = jobs[i][1];
        }

        // dp[i]: best profit we can have while deciding on jobs[i - 1]
        int[] dp = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            int start = jobs[i - 1][0];
            int currProfit = jobs[i - 1][2];
            // Number of jobs finished before start, so use upper bound.
            int k = upperBound(endTimes, start);
            dp[i] = Math.max(dp[i - 1], currProfit + dp[k]);
        }

        return dp[N];
    }

    private int upperBound(int[] values, int target) {
        int left = 0;
        int right = values.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (values[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

from bisect import bisect_right
from typing import List

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
        end_times = [job[1] for job in jobs]
        N = len(jobs)
        # dp[i]: best profit we can have while deciding on jobs[i-1]
        # Choices: skip current job and use dp[i-1] or take the job & add profit to previously finished jobs
        dp = [0] * (1 + N)
        for i in range(1, 1 + N):
            start, end, p = jobs[i-1]
            # Num of jobs finished before start, should be bisect_right!
            k = bisect_right(end_times, start)
            dp[i] = max(dp[i-1], p + dp[k])

        return dp[N]

1641. Count Sorted Vowel Strings

Dynamic programming

Let dp[i] count sorted strings of the current length that end with the ith vowel. Extending the strings by one character turns these counts into prefix sums because a vowel may follow only vowels that are no greater than it.

class Solution {
    public int countVowelStrings(int n) {
        int[] dp = {1, 1, 1, 1, 1};

        for (int length = 1; length < n; length++) {
            for (int i = 1; i < 5; i++) {
                dp[i] += dp[i - 1];
            }
        }

        int res = 0;
        for (int count : dp) {
            res += count;
        }
        return res;
    }
}

class Solution:
    def countVowelStrings(self, n: int) -> int:
        dp = [1] * 5

        for _ in range(1, n):
            for i in range(1, 5):
                dp[i] += dp[i - 1]

        return sum(dp)

Combinatorics

A sorted vowel string is fully determined by the number of times each vowel appears. This becomes a stars-and-bars problem: distribute n characters among five vowels, giving C(n + 4, 4).

class Solution {
    public int countVowelStrings(int n) {
        // A sorted vowel string is fully determined by how many times each vowel appears.
        // We have n objects and 4 dividers, so choose divider positions from n + 4 positions.
        return (n + 4) * (n + 3) * (n + 2) * (n + 1) / 24;
    }
}

class Solution:
    def countVowelStrings(self, n: int) -> int:
        # A sorted vowel string is fully determined by how many times each vowel appears.
        # We have n objects and 4 dividers, need to place dividers among (n+4) positions: C(n+4, 4)
        return (n + 4) * (n + 3) * (n + 2) * (n + 1) // 24

3693. Climbing Stairs II

Let dp[i] be the minimum total cost to reach stair i. The previous stair can be i - 1, i - 2, or i - 3; add the landing cost costs[i - 1] and the square of the jump length to each reachable previous state.

class Solution {
    public int climbStairs(int n, int[] costs) {
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            if (i == 1) {
                dp[i] = costs[i - 1] + 1;
            } else if (i == 2) {
                dp[i] = Math.min(
                    dp[1] + costs[i - 1] + 1,
                    dp[0] + costs[i - 1] + 4
                );
            } else {
                dp[i] = Math.min(
                    dp[i - 1] + costs[i - 1] + 1,
                    Math.min(
                        dp[i - 2] + costs[i - 1] + 4,
                        dp[i - 3] + costs[i - 1] + 9
                    )
                );
            }
        }

        return dp[dp.length - 1];
    }
}

from typing import List

class Solution:
    def climbStairs(self, n: int, costs: List[int]) -> int:
        #dp[i] = min(dp[i-1]+costs[i-1]+1, dp[i-2]+costs[i-1]+4, dp[i-3]+costs[i-1]+9)
        dp = [0] * (1 + n)

        for i in range(1, n+1):
            if i == 1:
                dp[i] = costs[i-1] + 1
            elif i == 2:
                dp[i] = min(dp[1]+costs[i-1]+1, dp[0]+costs[i-1]+4)
            else:
                dp[i] = min(dp[i-1]+costs[i-1]+1, dp[i-2]+costs[i-1]+4, dp[i-3]+costs[i-1]+9)

        return dp[-1]