Quy hoạch động 1 chiều — 1D Dynamic Programming

function dp1d(n: number, /* params */): R {
  const dp = new Array(n + 1).fill(initValue)
  dp[0] = baseCase0  // base case
  // dp[1] = baseCase1  // nếu cần

  for (let i = 1; i <= n; i++) {
    dp[i] = transition(dp[i - 1], dp[i - 2], /* ... */)
  }

  return dp[n]
}

// Tối ưu space O(1) nếu chỉ phụ thuộc 2 giá trị trước:
function dp1dOptimized(n: number): R {
  let prev2 = baseCase0
  let prev1 = baseCase1
  for (let i = 2; i <= n; i++) {
    const curr = transition(prev1, prev2)
    prev2 = prev1
    prev1 = curr
  }
  return prev1
}