Dynamic programming with memoization
Intuition\nThis is form of dynamic programing like 0/1 knapsacks. You have only two state is 0 (stay at the current city) or 1 (move to the other city). \n\n\n#
# Intuition\nThis is form of dynamic programing like 0/1 knapsacks. You have only two state is 0 (stay at the current city) or 1 (move to the other city). \n\n\n# Approach\n\nAt each city, you have dayRemain is repesention for num day remain to travel,  i is current city, idx is index of current day.\n\nIf you choose stay at the city, the score will be stayScore[idx][i] + \nmaxScore in next state (city is i, dayRemain - 1, idx + 1)\n\nIf you choose move to the next city, the score will be travelScore[i][j] + maxScore in next state (city is j, dayRemain - 1, idx + 1). You need iterate all city except current city i. \n\nAnd compare score when stay or travel -> return the max value \n\nFor short \nmaxScore(i, dayRemain, idx) = max (\n        stayScore[idx][i] + maxScore(i, dayRemain - 1, idx + 1),\n        max(travelScore[i][j], maxScore(i, dayRemain - 1, idx + 1)) for j from 0 to n, j != i\n    )\n\n\n# Complexity\n- Time complexity: O(n * n * k)\n\n- Space complexity: O(n * k)\n\n# Code\n```java []\nclass Solution {\n    Integer[][] memo;\n\n    public int maxScore(int n, int k, int[][] stayScore, int[][] travelScore) {\n        memo = new Integer[n][k];\n\n        int ret = 0;\n        for (int i = 0; i < n; i++) {\n            ret = Math.max(\n                    findMaxScore(i, k, 0, stayScore, travelScore),\n                    ret\n            );\n        }\n\n        return ret;\n    }\n\n    public int findMaxScore(int i, int dayRemain, int idx, int[][] stayScore, int[][] travelScore) {\n        if (dayRemain == 0) {\n            return 0;\n        }\n\n        if (memo[i][idx] != null) {\n            return memo[i][idx];\n        }\n\n\n        // score when stay at the city\n        int scoreStay = stayScore[idx][i] + findMaxScore(i, dayRemain - 1, idx + 1, stayScore, travelScore);\n\n        // score travel\n        int scoreTravel = 0;\n        for (int j = 0; j < travelScore.length; j++) {\n            if (i != j) {\n                scoreTravel = Math.max(\n                        scoreTravel,\n                        travelScore[i][j] + findMaxScore(j, dayRemain - 1, idx + 1, stayScore, travelScore)\n                );\n            }\n        }\n\n        return memo[i][idx] = Math.max(scoreTravel, scoreStay);\n    }\n}\n```
[]