Beats 100 % Maximum points tourist can earn in C++
Intuition\nThe problem involves maximizing scores over a series of days while either staying at a location or traveling to another. The goal is to choose action
# Intuition\nThe problem involves maximizing scores over a series of days while either staying at a location or traveling to another. The goal is to choose actions that yield the highest possible score after a given number of days.\n\n# Approach\nDynamic Programming Table:Use a 2D DP array dp where dp[d][C] represents the maximum score achievable on day d at location C.\nInitialize dp with zeros, indicating no score on the initial day at any location.\n\nFill the DP Table:\n\nFor each day d (from 0 to k-1):\nFor each location C (from 0 to n-1):\nUpdate the score for staying at the same location: dp[d + 1][C] = max(dp[d + 1][C], dp[d][C] + stayScore[d][C]).\nFor traveling to a different location W, check all other locations (W != C) and update: dp[d + 1][W] = max(dp[d + 1][W], dp[d][C] + travelScore[C][W]).\n\nFind the Maximum Score: After filling the DP table, iterate through the last day k to find the maximum score possible at any location.\n\nReturn the Result: The final result is the maximum score found on the last day.\n\n# Complexity\n- **Time complexity**:The outer loop runs for k days, and for each day, we iterate through n locations twice (once for staying and once for traveling). Thus, the time complexity is O(k\u22C5n 2).\n\n- **Space complexity**:The space complexity is O(k\u22C5n) for the DP table.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {\n        vector<vector<int>> dp(k + 1, vector<int>(n, 0));\n        for (int d = 0; d < k; d++) {\n            for (int C = 0; C < n; C++) {\n                dp[d + 1][C] = max(dp[d + 1][C], dp[d][C] + stayScore[d][C]);\n                for (int W = 0; W < n; W++) {\n                    if (C != W) { \n                        dp[d + 1][W] = max(dp[d + 1][W], dp[d][C] + travelScore[C][W]);\n                    }\n                }\n            }\n        }\n        int MP = 0;\n        for (int C = 0; C < n; C++) {\n            MP = max(MP, dp[k][C]);\n        }\n        return MP;\n    }\n};\n```
[]