[C++] Top down and Bottom up dp.
\ncpp []\nclass Solution {\npublic:\n    int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {\n        vector<vector<i
\n```cpp []\nclass Solution {\npublic:\n    int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {\n        vector<vector<int>> cached(k, vector<int>(n, -1));\n\n        function<int(int, int)> dfs = [&](int day, int city) -> int {\n            if (day == k) {\n                return 0;\n            }\n\n            if (cached[day][city] != -1) {\n                return cached[day][city];\n            }\n\n            int stay_score = stayScore[day][city] + dfs(day + 1, city);\n            int travel_score = 0;\n            for (int dest = 0; dest < n; ++dest) {\n                travel_score = max(travel_score, travelScore[city][dest] + dfs(day + 1, dest));\n            }\n\n            return cached[day][city] = max(stay_score, travel_score);\n        };\n\n        int ans = 0;\n        for (int i = 0; i < n; ++i) {\n            ans = max(ans, dfs(0, i));\n        }\n\n        return ans;\n    }\n};\n```\n\n```\nclass Solution {\npublic:\n    int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {\n        vector<vector<int>> dp(k, vector<int>(n));\n        int ans = 0;\n        for (int day = 0; day < k; ++day) {\n            for (int city = 0; city < n; ++city) {\n                dp[day][city] = max(dp[day][city], stayScore[day][city] + (day > 0 ? dp[day - 1][city] : 0));\n                for (int dest = 0; dest < n; ++dest) {\n                    dp[day][dest] = max(dp[day][dest], travelScore[city][dest] + (day > 0 ? dp[day - 1][city] : 0));\n                }\n            }\n        }\n\n        return *max_element(begin(dp[k - 1]), end(dp[k - 1]));\n    }\n};\n```\n\n
[]