Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

One-Dimensional DP

Guide 3 of 6 · Path 3 of 6

← PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumone-dimensional-dp

House Robber

Problem (restated)

Rob houses in a line; cannot rob adjacent houses. Maximize total money.

Intuition

At each house: rob it (+ skip previous) or skip it (take previous best).

Approaches

1D DP

Tested only
Time O(n)Space O(1)

Idea. dp[i] = max(dp[i-1], dp[i-2] + nums[i]); roll two vars.

Walkthrough. [2,7,9,3,1] → 2+9+1=12 or 7+3+… best 12.

Trade-offs. O(1) space after realizing only last two states matter.

Solution
export function rob(nums: number[]): number {
  let prev2 = 0, prev1 = 0;
  for (const x of nums) {
    const cur = Math.max(prev1, prev2 + x);
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

export function rob(nums: number[]): number {
  let prev2 = 0, prev1 = 0;
  for (const x of nums) {
    const cur = Math.max(prev1, prev2 + x);
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

Template connection

One-dimensional DP choose/skip.

Reflection