Simple CakeWalk DP Approach || Easy & Elegant Solution || With Explanation
\nint dp[201][201];\nclass Solution {\npublic:\n    int solve(int currCity, int currDay, int &n, int &k, vector<vector<int>>&ss, vector<vector<int>>&ts){\n     
```\nint dp[201][201];\nclass Solution {\npublic:\n    int solve(int currCity, int currDay, int &n, int &k, vector<vector<int>>&ss, vector<vector<int>>&ts){\n        if(currDay>=k){\n            return 0;\n        }\n        if(dp[currDay][currCity]!=-1) return dp[currDay][currCity];\n        // at every point of time we have two options if we have days left;\n        // 1. stay at current city on that day;\n        int op1 = ss[currDay][currCity] + solve(currCity,currDay+1,n,k,ss,ts);\n        // 2. option 2, move to another n-1 city\n        int op2 = 0;\n        for(int city=0;city<n;city++){\n            if(city==currCity) continue;\n            op2 = max(op2, ts[currCity][city] + solve(city,currDay+1,n,k,ss,ts));\n        }\n        \n        return dp[currDay][currCity] = max(op1,op2);\n    }\n    int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {\n        // this can be solve using dynamic programming approach;\n        memset(dp,-1,sizeof(dp));\n        int ans = 0;\n\t\t// we can start from any city from 0 to n-1, that\'s why try every city as an start City\n        for(int startCity=0;startCity<n;startCity++){\n            ans = max(ans,solve(startCity,0,n,k,stayScore,travelScore));\n        }\n        return ans;\n    }\n};\n```
[]