TypeScript || DP || T/S: 95% / 95%
Intuition\n Describe your first thoughts on how to solve this problem. \nWhen approaching this problem, I thought of using dynamic programming to maximize the s
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWhen approaching this problem, I thought of using dynamic programming to maximize the score based on the number of days and the available cities. The goal was to decide for each day whether to stay in the same city or travel to a different city, optimizing the total score. The challenge is to find a balance between staying and traveling while considering previous decisions for an optimal solution.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nI utilized dynamic programming (DP) to track the maximum score at each city for each day. The `dp` table holds the maximum score for each day and city, allowing us to make optimal choices for staying or traveling.\n\nFor the first day, I simply assigned the maximum score for staying or traveling to each city.\nFor subsequent days, I combined the score for staying in the current city with the maximum score from the previous day, while also considering travel options from all other cities.\nAt the end, the maximum score across all cities on the last day will be the final result.\n# Complexity\n- Time complexity:  $$O(k \xD7 n^2)$$\nWe iterate through each day (k), and for each day, we loop through each city (n) and compare it with all other cities (n), making this an $$O(n^2)$$ operation for each day.\n\n- Space complexity:  $$O(k \xD7 n)$$\nWe store the scores for each day and city in the dp table, which requires space proportional to the product of the number of days (k) and the number of cities (n).\n\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```typescript []\nfunction maxScore(n: number, k: number, stayScore: number[][], travelScore: number[][]): number {\n\n    const dp = Array.from({ length: k }, () => Array(n).fill(0));\n\n    for (let day = 0; day < k; day++) {\n        for (let currCity = 0; currCity < n; currCity++) {\n            let maxPoints\n            if (day === 0) {\n                maxPoints = stayScore[day][currCity]\n                for (let prevCity = 0; prevCity < n; prevCity++) {\n                    const travelPoints = travelScore[prevCity][currCity];\n                    maxPoints = Math.max(maxPoints, travelPoints);\n                }\n            } else {\n                maxPoints = stayScore[day][currCity] + dp[day - 1][currCity];\n                for (let prevCity = 0; prevCity < n; prevCity++) {\n                    const travelPoints = travelScore[prevCity][currCity];\n                    maxPoints = Math.max(maxPoints, dp[day - 1][prevCity] + travelPoints);\n\n                }\n            }\n\n\n            dp[day][currCity] = maxPoints;\n        }\n    }\n\n    return Math.max(...dp[k - 1]);\n};\n```\n\nThis approach efficiently calculates the maximum score while considering both staying and traveling options for each city and day.
[]