Skip to main content
HTML5ANDCSS3 logoHTML5ANDCSS3Tools and Tutorials

Dynamic Programming

1D Dynamic Programming

Written by Updated

1D DP means one array of state, where each entry is the best answer up to that index. If the answer at position i depends only on earlier positions, this is the shape.

House robber - non-adjacent choices

You cannot take two adjacent items. At each position: skip it and keep the previous best, or take it and add the best from two positions back.

House robber

javascript

function rob(nums) {
  let twoBack = 0   // best excluding the previous item
  let oneBack = 0   // best including everything up to the previous

  for (const n of nums) {
    const take = twoBack + n
    const skip = oneBack
    ;[twoBack, oneBack] = [oneBack, Math.max(take, skip)]
  }

  return oneBack
}

console.log(rob([2, 7, 9, 3, 1]))  // 12  (2 + 9 + 1)

Only two previous values are ever needed, so the array collapses to two variables - O(1) space. Make that reduction once you have the array version working, not before.

Longest increasing subsequence

LIS

javascript

function lengthOfLIS(nums) {
  if (nums.length === 0) return 0

  // best[i] = length of the longest increasing run ending at i.
  const best = new Array(nums.length).fill(1)

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        best[i] = Math.max(best[i], best[j] + 1)
      }
    }
  }

  return Math.max(...best)
}

console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))  // 4

O(n squared). There is an O(n log n) version using binary search over a tails array - worth mentioning if asked, but this one is the answer to write first.

Note that the answer is Math.max(...best), not best[n-1]. The longest run does not have to end at the last element.

Word break - DP over a string

Can the string be split into dictionary words?

javascript

function wordBreak(s, words) {
  const dictionary = new Set(words)
  // possible[i] = can s.slice(0, i) be formed?
  const possible = new Array(s.length + 1).fill(false)
  possible[0] = true   // empty string, trivially yes

  for (let end = 1; end <= s.length; end++) {
    for (let start = 0; start < end; start++) {
      if (possible[start] && dictionary.has(s.slice(start, end))) {
        possible[end] = true
        break
      }
    }
  }

  return possible[s.length]
}

console.log(wordBreak("leetcode", ["leet", "code"]))  // true
console.log(wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]))  // false

The second example is why greedy fails: taking "cats" first leaves "andog", which cannot be split. DP tries every split point, so it finds that "cat" + "sand" also dead-ends and correctly returns false.

Recognising 1D DP

  • The answer at position i depends on earlier positions only.
  • Phrases like "maximum", "minimum", "how many ways" over a sequence.
  • There is a choice at each step - take it or skip it.
  • Greedy fails because an early choice can block a better later one.
PreviousClassic DP ProblemsNext2D Dynamic Programming