8.24 - hard - 104

568. Maximum Vacation Days

又是一道dp，感觉用心去想还是可以做出来的，不过有点做不动了，看了答案，理解了一下。

class Solution(object):
    def maxVacationDays(self, flights, days):
        """
        :type flights: List[List[int]]
        :type days: List[List[int]]
        :rtype: int
        """
        # dp[i][j] - max days play if you spent week j in city i;
        # dp[i][j] = days[i][j] + max(dp[i=0,m][j + 1])
        n = len(days)
        k = len(days[0])
        dp = [[-sys.maxint for _ in range(k)] for _ in range(n)]
        
        for j in range(k-1, -1, -1):
            for i in range(n):  # 最后一周呆在某个城市所获得的收益
                dp[i][j] = days[i][j]
                for i1 in range(n):
                    if j < k - 1 and (flights[i][i1] or i == i1): # 从倒数第二周开始
                        dp[i][j] = max(dp[i][j], days[i][j] + dp[i1][j + 1])
        maxplay = dp[0][0]
        for i in range(n):
            if flights[0][i]:
                maxplay = max(maxplay, dp[i][0])
        return maxplay