Python | DP solution | Beats 60%
IntuitionApproachA brute force algorithm with recursion would try every possible situation and deduce the optimal score. We can do something similar but with DP
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->Since this is an optimization problem where we have to make decision (that is stay in same city or move to a different city), this is a Dynamic Programming problem.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nA brute force algorithm with recursion would try every possible situation and deduce the optimal score. We can do something similar but with DP. \n\nThe 2d array `DP[i][j]` (of size `(k+1) x n`) would store the maximum score till day `i` if at day `i` we were in city `j`.\n\nFor the first day, i.e `i = 1`, we would need to find, for each city `j`, which is maximum: Starting from that city and staying in that city (i.e `stayScore[0][j]`) `OR` starting from any other city `k` and travelling to `j` (i.e `travelScore[k][j]` for each possible `k`)\n\nThis would initialize the DP array. \n\nNow from 2nd day onward, that is from day `i=2` onward, we can follow this relation:\n\n`DP[i][j] = max(DP[i-1][j] + stayScore[i-1][j], max(DP[i-1][k] + travelScore[k][j] for each city k other than j))`\n\n\nand finally at last, we can return the maximum value in the last row of `DP` (i.e `max(DP[-1])`).\n\n\n# Complexity\n- Time complexity:$$O(kn^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: $$O(kn)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\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] * n for _ in range(k+1)]\n\n        for j in range(n):\n            dp[1][j] = stayScore[0][j]\n            for i in range(n):\n                dp[1][j] = max(dp[1][j], travelScore[i][j])\n        \n\n        for i in range(2, k+1):\n            for j in range(n):\n                for k in range(n):\n                    if k == j:\n                        dp[i][j] = max(dp[i][j], dp[i-1][j] + stayScore[i-1][j])\n                    else:\n                        dp[i][j] = max(dp[i][j], dp[i-1][k] + travelScore[k][j])\n        \n        return max(dp[-1])\n        \n\n```
['Dynamic Programming', 'Recursion', 'Python3']