最大休假次数。
力扣想让一个最优秀的员工在 N 个城市间旅行来收集算法问题。
但只工作不玩耍，聪明的孩子也会变傻，所以您可以在某些特定的城市和星期休假。
您的工作就是安排旅行使得最大化你可以休假的天数，但是您需要遵守一些规则和限制。
规则和限制：
您只能在 N 个城市之间旅行，用 0 到 N-1 的索引表示。一开始，您在索引为0的城市，并且那天是星期一。
这些城市通过航班相连。这些航班用 NN 矩阵 flights（不一定是对称的）表示，flights[i][j] 代表城市i到城市j的航空状态。如果没有城市i到城市j的航班，flights[i][j] = 0；否则，flights[i][j] = 1。同时，对于所有的 i，flights[i][i] = 0。
您总共有 K 周（每周7天）的时间旅行。您每天最多只能乘坐一次航班，并且只能在每周的星期一上午乘坐航班。由于飞行时间很短，我们不考虑飞行时间的影响。
对于每个城市，不同的星期您休假天数是不同的，给定一个 NK 矩阵 days 代表这种限制，days[i][j] 代表您在第j个星期在城市i能休假的最长天数。
给定 flights 矩阵和 days 矩阵，您需要输出 K 周内可以休假的最长天数。
力扣568。
动态规划。具体见代码。
代码用golang编写。代码如下：
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
}
}执行结果如下：
