题解 | 气球谜题

感谢大佬提供的思路，使用动态规划管理共15种状态，实际上每种状态的前置状态最多会有2种，理解了这一点状态转移方程就不难得出了

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    let n = +(await readline())
    const bullon = (await readline()).split('').map(Number)
    const t = (await readline()).split(' ').map(Number)
    const dp = new Array(n + 1).fill().map(() => new Array(15).fill(Infinity))
    // dp[i][j]表示把前i个气球染成状态j 所需的最少染色时间
    // j共有15种状态
    // dp[i][0]表示0， dp[i][1] - 1, dp[i][2] - 2
    // dp[3] - 01   dp[4] - 02     dp[5] - 12    dp[6] - 10    dp[7] - 20  dp[8] - 21
    // dp[9] - 012   dp[10] - 021   dp[11] - 102  dp[12] - 120   dp[13] - 201  dp[14] - 210
    // dp数组总共15种状态
    for(let i = 0; i < 3; i++)  dp[0][i] = 0
    for(let i = 1; i <= n; i++) {
        // 将第i个气球染成颜色0/1/2所需染色时间
        const cost = new Array(3).fill(t[i - 1])
        cost[bullon[i - 1]] = 0 // 若原本就为bullon[i-1]，则染色时间为0
        dp[i][0] = dp[i - 1][0] + cost[0] // 0 -> 0
        dp[i][1] = dp[i - 1][1] + cost[1] // 1 -> 1
        dp[i][2] = dp[i - 1][2] + cost[2] // 2 -> 2
        // 有2个气球及以上才可能出现3-8的状态
        if(i >= 2) {
            dp[i][3] = Math.min(dp[i - 1][0], dp[i - 1][3]) + cost[1] // 0/01  ->  01
            dp[i][4] = Math.min(dp[i - 1][0], dp[i - 1][4]) + cost[2] // 0/02  ->  02
            dp[i][5] = Math.min(dp[i - 1][1], dp[i - 1][5]) + cost[2] // 1/12  ->  12
            dp[i][6] = Math.min(dp[i - 1][1], dp[i - 1][6]) + cost[0] // 1/10  ->  10
            dp[i][7] = Math.min(dp[i - 1][2], dp[i - 1][7]) + cost[0] // 2/20  ->  20
            dp[i][8] = Math.min(dp[i - 1][2], dp[i - 1][8]) + cost[1] // 2/21  ->  21
        }
        // 有3个及以上气球才可能出现9-14的状态
        if(i >= 3) {
            dp[i][9] = Math.min(dp[i - 1][3], dp[i - 1][9]) + cost[2] // 01/012 -> 012
            dp[i][10] = Math.min(dp[i - 1][4], dp[i - 1][10]) + cost[1] // 02/021 -> 021
            dp[i][11] = Math.min(dp[i - 1][6], dp[i - 1][11]) + cost[2] // 10/102 -> 102
            dp[i][12] = Math.min(dp[i - 1][5], dp[i - 1][12]) + cost[0] // 12/120 -> 120
            dp[i][13] = Math.min(dp[i - 1][7], dp[i - 1][13]) + cost[1] // 20/201 -> 201
            dp[i][14] = Math.min(dp[i - 1][8], dp[i - 1][14]) + cost[0] // 21/210 -> 210
        }
    }
    let res = Infinity
    for(let i = 0; i < 15; i++) {
        res = Math.min(dp[n][i], res)
    }
    console.log(res)
}();