LeetCode 568. 最大休假天数（DP）

示例 1:
输入:flights = [[0,1,1],[1,0,1],[1,1,0]], 
days = [[1,3,1],[6,0,3],[3,3,3]]
输出: 12
解释: 
Ans = 6 + 3 + 3 = 12. 
最好的策略之一：
第一个星期 : 星期一从城市0飞到城市1，玩6天，工作1天。 
（虽然你是从城市0开始，但因为是星期一，我们也可以飞到其他城市。） 
第二个星期 : 星期一从城市1飞到城市2，玩3天，工作4天。
第三个星期 : 呆在城市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 {
public:
    int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
    	int dp[100][100];// 在 i 城市时， 是第 k 周， 最多休假天数
    	memset(dp, 0xff, sizeof(dp));
        int n = flights.size(), k = days[0].size(), maxdays = 0;
    	for(int i = 0; i < n; ++i)
    	{
            //可以待在原地不走
    		flights[i][i] = 1;
    	}    	
    	for(int i = 0; i < n; ++i)//初始化第0周
    	{
    		if(flights[0][i])//0城市可以飞到i城市
    		{
                dp[i][0] = days[i][0];
                maxdays = max(maxdays, dp[i][0]);
            }
    	}
    	for(int wk = 1; wk < k; ++wk)//遍历剩余的周
    	{
    		for(int i = 0; i < n; ++i)//遍历每个城市
    		{
    			if(dp[i][wk-1] == -1)//上周i城市的状态不存在
    				continue;
    			for(int j = 0; j < n; ++j)//我要去 j 城市
    			{
    				if(!flights[i][j])//没有航班，不行
    					continue;
    				dp[j][wk] = max(dp[j][wk], dp[i][wk-1]+days[j][wk]);
                    maxdays = max(maxdays, dp[j][wk]);
    			}
    		}
    	}
    	return maxdays;
    }
};