---
title: "Dynamic programming (1-D)"
url: https://algopath.pro/patterns/dynamic-programming
language: en
summary: "Answer a small version of the problem, store the result, then build the next one from that. Every state is computed once."
updated: 2026-08-24
---

# Dynamic programming (1-D)

Answer a small version of the problem, store the result, then build the next one from that. Every state is computed once.

## 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.

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

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

- 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

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

- **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.

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

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

## 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.

```javascript
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;
}
```

## 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)?

- **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.

## JavaScript

```javascript
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;
}
```

## Python

```python
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
```

## PHP

```php
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;
}
```