function packageMaxWeight(bagWeight: number, values: number[], weights: number[]) {
  const array2d: number[][] = [[]]
  for (let j = 0; j <= bagWeight; j++) {
    array2d[0][j] = j >= weights[0] ? values[0] : 0
  }
  for (let i = 1; i < values.length; i++) {
    array2d[i] = []
    for (let j = 0; j <= bagWeight; j++) {
      if (j < weights[i]) {
        array2d[i][j] = array2d[i - 1][j]
        continue
      }
      array2d[i][j] = Math.max(values[i] + array2d[i - 1][j - weights[i]], array2d[i - 1][j])
    }
  }
  return { result: array2d[values.length - 1][bagWeight], array2d }
}
const { result, array2d } = packageMaxWeight(6, [5, 6, 6, 10, 4, 4], [2, 1, 4, 6, 3, 5])
console.info('result:', result)
console.table(array2d)
      

function climbStairs(n: number): number {
  const arr = [1, 2]
  for (let i = 2; i < n; i++) {
      arr[i] = arr[i - 1] + arr[i - 2]
  }
  return arr[n - 1]
};
      

function mostPoints(questions: number[][]): number {
  const dp: number[] = []
  const len = questions.length
  for (let m = len - 1; m >= 0; m--) {
    const end = m + questions[m][1] + 1
    dp[m] = questions[m][0]
    if (end < len) {
      dp[m] = questions[m][0] + dp[end]
    }
    if (m < len - 1) {
      dp[m] = Math.max(dp[m], dp[m + 1])
    }
  }
  return dp[0]
}
      

function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
  const m = obstacleGrid.length
  const n = obstacleGrid[0].length
  if (obstacleGrid[0][0] === 1) return 0
  const dp: number[][] = [[1]]

  for (let i = 1; i < m; i++) {
    if (obstacleGrid[i][0] === 1) {
      dp[i] = [0]
    } else {
      dp[i] = [dp[i - 1][0]]
    }
  }

  for (let i = 1; i < n; i++) {
    if (obstacleGrid[0][i] === 1) {
      dp[0][i] = 0
    } else {
      dp[0][i] = dp[0][i - 1]
    }
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (obstacleGrid[i][j] === 1) {
        dp[i][j] = 0
      } else {
        dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
      }
    }
  }
  return dp[m - 1][n - 1]
}