Beats 100% in time and Space complexity
\n\n# Approach\nDefine the DP Table:\n\nWe create a 2D dp array where dp[days][curr] represents the maximum score achievable starting from curr city on days day
\n\n# Approach\nDefine the DP Table:\n\nWe create a 2D dp array where dp[days][curr] represents the maximum score achievable starting from curr city on days day until the end.\ndp has dimensions (k + 1) x n where k is the number of days and n is the number of cities.\n\nBottom-Up DP Approach:\n\nSince we want to find the maximum possible score by the time we reach day 0, we compute dp values starting from the last day (k - 1) and move backward to 0.\nFor each day days from k - 1 to 0, we:\nOption 1: Stay in the Current City:\nIf the tourist stays in city curr on day days, the score gained will be stayScore[days][curr] + dp[days + 1][curr].\nOption 2: Travel to Another City:\nFor every other city i, if the tourist travels from curr to i, the score gained will be travelScore[curr][i] + dp[days + 1][i].\nThe best option (either staying or traveling) is stored in dp[days][curr].\nCalculate the Result:\n\nAfter filling the dp table, the maximum score starting from any city on day 0 is the answer. This is the maximum value in dp[0][curr] for all cities curr.\n\n# Complexity\n- Time complexity:\nO(k\xD7n^2)\n- Space complexity:\nO(k\xD7n)\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\n      \n        for (int days = k - 1; days >= 0; days--) {\n            for (int curr = 0; curr < n; curr++) {\n               \n                int ans = stayScore[days][curr] + dp[days + 1][curr];\n\n              \n                for (int i = 0; i < n; i++) {\n                    if (i != curr) {\n                        ans = max(ans, travelScore[curr][i] + dp[days + 1][i]);\n                    }\n                }\n                \n              \n                dp[days][curr] = ans;\n            }\n        }\n\n       \n        int maxScore = 0;\n        for (int curr = 0; curr < n; curr++) {\n            maxScore = max(maxScore, dp[0][curr]);\n        }\n\n        return maxScore;\n    }\n};\n\n```
[]