Simple and Easy JAVA Solution using DP Tabulation and Memoization
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\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)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\n// Tabulation\nclass Solution {\n    public int maxScore(int n, int k, int[][] stayScore, int[][] travelScore) {\n        int dp[][] = new int[k+1][n];\n        int ans = 0;\n        for(int day=0;day<k;day++){\n            for(int city=0;city<n;city++){\n                dp[day + 1][city] = Math.max(dp[day + 1][city],stayScore[day][city] + dp[day][city]);\n                for(int dest=0;dest<n;dest++){\n                    if(dest != city){\n                        dp[day + 1][dest] = Math.max(dp[day + 1][dest] , travelScore[city][dest] + dp[day][city]);\n                    }\n                }\n            }\n        }\n \n        for(int i=0;i<n;i++)\n            ans = Math.max(ans,dp[k][i]);\n\n        return ans;\n    }\n}\n\n// Memoization\nclass Solution {\n    public int maxScore(int n, int k, int[][] stayScore, int[][] travelScore) {\n        Integer dp[][] = new Integer[k][n];\n        int ans = 0;\n        for(int i=0;i<n;i++){\n            ans = Math.max(ans,helper(n,k,0,i,stayScore,travelScore,dp));\n        }\n        return ans;\n    }\n\n    private static int helper(int n,int k,int day,int city,int stayScore[][],int travelScore[][],Integer dp[][]){\n        if(day >= k){\n            return 0;\n        }\n\n        if(dp[day][city] != null)\n            return dp[day][city];\n\n        dp[day][city] = stayScore[day][city] + helper(n,k,day+1,city,stayScore,travelScore,dp);\n        for(int i=0;i<n;i++){\n            if(i != city)\n                dp[day][city] = Math.max(dp[day][city],travelScore[city][i] + helper(n,k,day+1,i,stayScore,travelScore,dp));\n        }\n\n        return dp[day][city];\n    }\n}\n```
[]