1D Dynamic Programming

Written by Swapnil RajaPublished 28 Aug 2026

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)

PreviousClassic DP Problems Next2D Dynamic Programming

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

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

1D Dynamic Programming

House robber - non-adjacent choices

Longest increasing subsequence

Word break - DP over a string

Recognising 1D DP