Simple Python DP Solution explained || Beats 88%
Intuition\n- Starting from the last day k-1, we calculate the points which can be accumulated for each city. This is the maximum of either staying in the same c
# Intuition\n- Starting from the last day $$k-1$$, we calculate the points which can be accumulated for each city. This is the maximum of either staying in the same city or travelleing to another city.\n- Next we move back a day, for $$k-2$$ we again check maximum of either staying or travelling, but now we also add the points from $$k-1$$ day of the city we reach at the end of $$k-2$$ days. \n- Keep doing this until we reach the first day and take the maximum points\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Initialize a DP table, of size $$n * (k+1)$$ with 0\n- Start from the last column $$k-1$$, iterate through each city $$j$$ and calculate max of either staying in $$j$$ or moving to another city, and add the points collected if we are at city $$j$$ on the next day\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nSince for each day $$k$$, we check all the cities $$n$$, and for each city we check what is the travel distance to all other cities $$n$$, time complexity should be $$O(k*n^2)$$ \n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n^2)$$\n# Code\n```python3 []\nclass Solution:\n    def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:\n        dp = [[0 for i in range(k+1)] for j in range(n)]\n        ans = 0\n        for i in range(k-1,-1,-1):\n            for j in range(n-1,-1,-1):\n                maxPoints = 0\n                #Check points if we stayed in the same city. We also add the points collected if we are in the city j from i+1 days. \n                maxPoints = max(maxPoints,stayScore[i][j]+dp[j][i+1])\n                for city in range(n):\n                    #Check points if we travelled to all the other n cities. We also add the points collected in that city from i+1 days\n                    maxPoints = max(maxPoints, travelScore[j][city] + dp[city][i+1])\n                dp[j][i] = maxPoints\n                ans = max(maxPoints,ans)\n        return ans\n```
[]