C++, Top-Down DP looks much more intuitive
Intuition\n Describe your first thoughts on how to solve this problem. \nBy following the description of the problem, and then the cache data structure can be c
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBy following the description of the problem, and then the cache data structure can be created based on variable input parameters of recursive function.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n*k)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n*k)\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {\n        int r=0;\n        vector<vector<int>> cache(n,vector<int>(k,-1));\n        for(int city=0;city<n;++city) //test on different starting city\n         r=max(r, solve(n, k, stayScore, travelScore, city,k-1,cache));\n        \n        return r;\n    }\n\n    int solve(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore, int city, int day,vector<vector<int>> &cache)\n    {\n        if(day<0) return 0;\n        int& res = cache[city][day];\n        if(res>=0) return res;\n\n        int r= solve(n,k,stayScore,travelScore,city,day-1,cache)+stayScore[day][city]; //stay in same city\n\n        for(int from=0;from<n;++from)\n              r=max(r, solve(n,k,stayScore,travelScore,from,day-1,cache)+travelScore[from][city]); //from other city\n\n        return res=r;\n    }\n};\n```
[]