题目

力扣想让一个最优秀的员工在 N 个城市间旅行来收集算法问题。 但只工作不玩耍，聪明的孩子也会变傻，所以您可以在某些特定的城市和星期休假。您的工作就是安排旅行使得最大化你可以休假的天数，但是您需要遵守一些规则和限制。

规则和限制：

  1. 您只能在 N 个城市之间旅行，用 0 到 N-1 的索引表示。一开始，您在索引为0的城市，并且那天是星期一。
  2. 这些城市通过航班相连。这些航班用 N*N 矩阵 flights（不一定是对称的）表示，flights[i][j] 代表城市i到城市j的航空状态。如果没有城市i到城市j的航班，flights[i][j] = 0；否则，flights[i][j] = 1。同时，对于所有的i，flights[i][i] = 0。
  3. 您总共有 K 周（每周7天）的时间旅行。您每天最多只能乘坐一次航班，并且只能在每周的星期一上午乘坐航班。由于飞行时间很短，我们不考虑飞行时间的影响。
  4. 对于每个城市，不同的星期您休假天数是不同的，给定一个 N*K 矩阵 days 代表这种限制，days[i][j] 代表您在第j个星期在城市i能休假的最长天数。

给定 flights 矩阵和 days 矩阵，您需要输出 K 周内可以休假的最长天数。

示例 1:

  1. 输入:flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
  2. 输出: 12
  3. 解释: 
  4. Ans = 6 + 3 + 3 = 12. 
  6. 最好的策略之一：
  7. 第一个星期 : 星期一从城市0飞到城市1，玩6天，工作1天。 
  8. （虽然你是从城市0开始，但因为是星期一，我们也可以飞到其他城市。） 
  9. 第二个星期 : 星期一从城市1飞到城市2，玩3天，工作4天。
  10. 第三个星期 : 呆在城市2，玩3天，工作4天。

示例 2:

输入:flights = [[0,0,0],[0,0,0],[0,0,0]], days = [[1,1,1],[7,7,7],[7,7,7]]
输出: 3
解释: 
Ans = 1 + 1 + 1 = 3. 

由于没有航班可以让您飞到其他城市，你必须在城市0呆整整3个星期。 
对于每一个星期，你只有一天时间玩，剩下六天都要工作。 
所以最大休假天数为3.

示例 3:

输入:flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[7,0,0],[0,7,0],[0,0,7]]
输出: 21
解释:
Ans = 7 + 7 + 7 = 21

最好的策略之一是：
第一个星期 : 呆在城市0，玩7天。 
第二个星期 : 星期一从城市0飞到城市1，玩7天。
第三个星期 : 星期一从城市1飞到城市2，玩7天。

注意:

  • N 和 K 都是正整数，在 [1, 100] 范围内。
  • 矩阵 flights 的所有值都是 [0, 1] 范围内的整数。
  • 矩阵 days 的所有值都是 [0, 7] 范围内的整数。
  • 超过休假天数您仍可以呆在那个城市，但是在额外的日子您需要 工作 ，这些日子不会算做休假日。
  • 如果您从城市A飞往城市B并在当天休假日，这个休假会被算作是城市B的休假日。
  • 我们不考虑飞行时间对计算休假日的影响。

方案一（动态规划）

class Solution:
    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
        # 无法使用贪心策略，贪心策略只会得到局部最优解
        # dp[i][j] 代表第i周在城市j进行休假所能取得的最大休假天数
        K = len(days[0])  # 总共的星期数
        N = len(flights)  # 航班数/城市数
        dp = [[-1]*N for _ in range(K)]

        # 初始化
        for i in range(N):
            # 可以飞到另一个城市，或在本城市
            if flights[0][i] or i == 0:
                dp[0][i] = days[i][0]

        for i in range(1, K):  # 第 i 周
            for j in range(N):  # 航班
                for city, day in enumerate(dp[i - 1]):  # 当前所在城市
                    if (flights[city][j] or city == j) and day != -1: # day != -1 表示上周不在那个城市
                        dp[i][j] = max(dp[i][j], day+days[j][i])

        return max(dp[K - 1])

递推方程

最大休假天数 - 图1#card=math&code=dp%5Bi%5D%5Bj%5D%20%3D%20max%28dp%5Bi%5D%5Bj%5D%2C%20dp%5Bi-1%5D%5Bj%5D%2Bdays%5Bj%5D%5Bi%5D%29&height=18&id=759a13a4&width=300)

第 i 周；在第 j 个城市

原文

https://leetcode-cn.com/explore/interview/card/google-interview/76/dynamic-programming/260/