Dynamic programming (1-D)

How does Dynamic programming (1-D) work?

Decide what one state means. Usually it is the best answer over the first i items.

Write the transition: how state i follows from earlier ones. That transition is the whole algorithm.

Fill the base cases by hand. Those are the states with nothing smaller to lean on.

Loop forward and fill the table in order. Every state it reads is already finished.

The answer is one cell, usually the last. Sometimes it is the largest cell in the table.

If the transition looks only two states back, keep two variables. The array is then unnecessary.

Sources: Wikipedia: Dynamic programming, Bellman (1954), The theory of dynamic programming

1. dp[0] = 2Robbing houses [2, 7, 9]. Taking only the first gives 2.
2. dp[1] = 7Take the better of 2 and 7. Neighbouring houses cannot both be robbed.
3. dp[2] = max(7, 2 + 9)Either skip the third house, or take it plus dp[0].
4. dp[2] = 11Taking the first and third houses wins.
5. answer = 11Three states, each computed exactly once.

function maxSubarraySum(nums) {
    let best = nums[0];
    let curr = nums[0];
    for (let i = 1; i < nums.length; i++) {
        curr = Math.max(nums[i], curr + nums[i]);
        best = Math.max(best, curr);
    }
    return best;
}

function maxSubarraySum(nums: number[]): number {
    let best = nums[0];
    let curr = nums[0];
    for (let i = 1; i < nums.length; i++) {
        curr = Math.max(nums[i], curr + nums[i]);
        best = Math.max(best, curr);
    }
    return best;
}

def max_subarray_sum(nums):
    best = curr = nums[0]
    for x in nums[1:]:
        curr = max(x, curr + x)
        best = max(best, curr)
    return best

function maxSubarraySum(array $nums): int {
    $best = $curr = $nums[0];
    for ($i = 1; $i < count($nums); $i++) {
        $curr = max($nums[$i], $curr + $nums[$i]);
        $best = max($best, $curr);
    }
    return $best;
}

    public static int maxSubarraySum(int[] nums) {
        int best = nums[0];
        int curr = nums[0];
        for (int i = 1; i < nums.length; i++) {
            curr = Math.max(nums[i], curr + nums[i]);
            best = Math.max(best, curr);
        }
        return best;
    }

    public static int MaxSubarraySum(int[] nums) {
        int best = nums[0];
        int curr = nums[0];
        for (int i = 1; i < nums.Length; i++) {
            curr = Math.Max(nums[i], curr + nums[i]);
            best = Math.Max(best, curr);
        }
        return best;
    }

A worked example of Dynamic programming (1-D)

Largest sum of a contiguous stretch

Return the largest sum of any contiguous stretch of an array.

Values can be negative, so the answer is not simply the total.

Let state i be the best sum of a stretch that ends at index i.

Either the previous stretch continues, or a new one starts here. The answer is the largest state.

function maxSubArray(nums) {
    let best = nums[0];
    let endingHere = nums[0]; // only the previous state matters, so no array

    for (let i = 1; i < nums.length; i++) {
        // continue the stretch, or start a new one right here
        endingHere = Math.max(nums[i], endingHere + nums[i]);
        best = Math.max(best, endingHere);
    }

    return best;
}

When should you use Dynamic programming (1-D)?

Use Dynamic programming (1-D) when the problem statement says “best/maximum/minimum ending at position i”, “ways to reach, climb, or tile” or “cannot pick two adjacent items”. A solution built on it usually runs in O(states).

• •best/maximum/minimum ending at position i
• •ways to reach, climb, or tile
• •cannot pick two adjacent items
• •minimum cost path through a grid
• •overlapping subproblems, same state recomputed

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Dynamic programming (1-D) confused with?

Dynamic programming (1-D) is most often confused with Recursion with memoization, Greedy (exchange argument), Recursion and DP on subsequences (LIS / LCS / edit distance).

• Recursion with memoization: Memoisation fills the same table from the top, on demand. This fills it upward in a fixed order.
• Greedy (exchange argument): Greedy commits to one choice per step. DP keeps every option until the end.
• Recursion: The recursion tells you what the transition is. The table is what makes it fast.
• DP on subsequences (LIS / LCS / edit distance): There the state is a pair of positions in two sequences. Here one index is enough.

Common mistakes with Dynamic programming (1-D)

• A state that does not decide the future

  If two situations share a state but behave differently, the state is incomplete. Add what is missing.

• Filling the table in the wrong order

  A cell has to be written before anything reads it. Follow the direction the transition needs.

• Reading the wrong cell as the answer

  For a best-ending-here state the answer is the maximum. It is not the last cell.

• Forgetting the base cases

  An empty or single-element input is where most of these break. Handle those first.

Which interview problems use Dynamic programming (1-D)?

Interview problems solved with Dynamic programming (1-D) include Climbing stairs, House robber, Maximum subarray, Coin change, Decode ways, Min cost climbing stairs and Fibonacci.

• Climbing stairs: Each step comes from one or two behind.
• House robber: Take this house plus two back, or skip it.
• Maximum subarray: Continue the stretch or start a new one.
• Coin change: The state is the amount, and every coin is a branch.
• Decode ways: One digit or two, when the pair is valid.
• Min cost climbing stairs: The same shape with a cost on each step.
• Fibonacci: The shortest transition there is.

What is the time and space complexity of Dynamic programming (1-D)?

The target complexity of Dynamic programming (1-D) is O(states).

n states with O(1) work each gives O(n). Memory drops to O(1) when only the last states matter.