2022-02-18：最大休假次数。

package main

import "fmt"

func main() {
    flights := [][]int{{0, 1, 1}, {1, 0, 1}, {1, 1, 0}}
    days := [][]int{{1, 3, 1}, {6, 0, 3}, {3, 3, 3}}
    ret := maxVacationDays(flights, days)
    fmt.Println(ret)
}

func maxVacationDays(fly, day [][]int) int {
    n := len(fly)
    k := len(day[0])
    // pas[i] = {a, b, c}
    // 从a、b、c能飞到i
    pass := make([][]int, n)
    for i := 0; i < n; i++ {
        s := 0
        for j := 0; j < n; j++ {
            if fly[j][i] != 0 {
                s++
            }
        }
        pass[i] = make([]int, s)
        for j := n - 1; j >= 0; j-- {
            if fly[j][i] != 0 {
                s--
                pass[i][s] = j
            }
        }
    }
    // dp[i][j] -> 第i周必须在j这座城，0~i-1周（随意），最大休假天数
    dp := make([][]int, k)
    for i := 0; i < k; i++ {
        dp[i] = make([]int, n)
    }
    // 飞的时机，是周一早上飞，认为对时间没有影响，直接到某个城，然后过一周
    dp[0][0] = day[0][0]
    for j := 1; j < n; j++ {
        if fly[0][j] != 0 {
            dp[0][j] = day[j][0]
        } else {
            dp[0][j] = -1
        }
    }
    for i := 1; i < k; i++ { // 第i周
        for j := 0; j < n; j++ { // 在j号城过！
            // 第i周，要怎么到j号城
            // 下面max的初始值，我第i-1周，就在j号城，选择不动地方，进入第i周
            max := dp[i-1][j]
            for _, p := range pass[j] { // 枚举什么？能到j号城的城市p
                max = getMax(max, dp[i-1][p])
            }
            if max != -1 {
                dp[i][j] = max + day[j][i]
            } else {
                dp[i][j] = -1
            }
        }
    }
    ans := 0
    for i := 0; i < n; i++ {
        ans = getMax(ans, dp[k-1][i])
    }
    return ans
}

func getMax(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}