Easy Java Solution (recursion + 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: O(n*k)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n*k + k)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int maxScore(int n, int k, int[][] stayScore, int[][] travelScore) {\n        return solution(n, k, stayScore, travelScore);\n    }\n\n\n    // recursion + memoization\n    public int solution(int n, int k, int[][] stayScore, int[][] travelScore) {\n        int[][] memo = new int[k][n];\n        for(int i=0;i<k;i++) {\n            for(int j=0;j<n;j++) {\n                memo[i][j] = -1;\n            }\n        }\n\n        // start your journey from any of the city\n        int maxScore = 0;\n        for(int i=0;i<n;i++) {\n            int score = funRec(0, i, n, k, stayScore, travelScore, memo);\n            maxScore = Math.max(maxScore, score);\n        }\n\n        return maxScore;\n    }\n\n\n    // time -> O(n*k), space -> O(n*k + k) : n*k for filling the memo table & k for recursion stack space\n    public int funRec(int currDay, int currCity, int n, int k, int[][] stayScore, int[][] travelScore, int[][] memo) {\n        \n        // base case\n        if(currDay >= k) {\n            return 0;\n        }\n        \n        if(memo[currDay][currCity] != -1)\n            return memo[currDay][currCity];\n\n        // stay in the same city\n        int score_for_staying = stayScore[currDay][currCity] + funRec(currDay + 1, currCity, n, k, stayScore, travelScore, memo);\n\n        // travel to city \'i\'\n        int score_for_travelling = 0;\n        for(int i=0;i<n;i++) {\n            int score = travelScore[currCity][i] + funRec(currDay+1, i, n,k, stayScore, travelScore, memo);\n\n            score_for_travelling = Math.max(score_for_travelling, score);\n        }\n\n        return  memo[currDay][currCity] = Math.max(score_for_staying, score_for_travelling);\n    }\n}\n```
[]