Paint House

Description

null

Solution(javascript)

// /** 1: Top-down
//  * @param {number[][]} costs
//  * @return {number}
//  */
// const minCost = function (costs) {
//   const map = {
//     0: [1, 2],
//     1: [0, 2],
//     2: [0, 1],
//   }
//   const memo = []
//   const aux = (index, color) => {
//     memo[index] = memo[index] || []
//     if (memo[index][color] !== undefined) {
//       return memo[index][color]
//     }
//     if (index >= costs.length) {
//       return 0
//     }
//     memo[index][color] = costs[index][color] + Math.min(
//       ...map[color].map(nextColor => aux(index + 1, nextColor)),
//     )
//     return memo[index][color]
//   }
//   return Math.min(
//     aux(0, 0),
//     aux(0, 1),
//     aux(0, 2),
//   )
// }

/** 1: Bottom-up
 * @param {number[][]} costs
 * @return {number}
 */
const minCost = function (costs) {
  const map = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1],
  }
  let memo = [0, 0, 0]

  for (let i = costs.length - 1; i >= 0; i--) {
    const current = []
    for (let color = 0; color < 3; color++) {
      current[color] = costs[i][color] + Math.min(
        ...map[color].map(nextColor => memo[nextColor]),
      )
    }
    memo = current
  }
  return Math.min(
    ...memo,
  )
}