Paint House II

Description

null

Solution(javascript)

// /** 1: Dp O(nk^2)
//  * @param {number[][]} costs
//  * @return {number}
//  */
// const minCostII = function (costs) {
//   if (!costs.length) {
//     return 0
//   }
//   const k = costs[0].length
//   let memo = new Array(k).fill(0)

//   const getMin = (color) => {
//     let min = Infinity
//     for (let i = 0; i < k; i++) {
//       if (i !== color) {
//         min = Math.min(
//           min,
//           memo[i],
//         )
//       }
//     }
//     return min === Infinity ? 0 : min
//   }
//   for (let i = costs.length - 1; i >= 0; i--) {
//     const current = []
//     for (let color = 0; color < k; color++) {
//       current[color] = costs[i][color] + getMin(color)
//     }
//     memo = current
//   }
//   return Math.min(
//     ...memo,
//   )
// }


/** 1: Dp O(nk)
 * @param {number[][]} costs
 * @return {number}
 */
const minCostII = function (costs) {
  if (!costs.length) {
    return 0
  }
  const k = costs[0].length

  let min1 = [0, null]
  let min2 = [0, null]
  for (let i = costs.length - 1; i >= 0; i--) {
    let current1 = null
    let current2 = null
    for (let color = 0; color < k; color++) {
      let currentCost = costs[i][color]
      if (color !== min1[1]) {
        currentCost += min1[0]
      } else {
        currentCost += min2[0]
      }

      if (current1 === null || currentCost < current1[0]) {
        current2 = current1
        current1 = [currentCost, color]
      } else if (current2 === null || currentCost < current2[0]) {
        current2 = [currentCost, color]
      }
    }
    min1 = current1
    min2 = current2
  }
  return min1[0]
}