Simple 1D JAVA DP, beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nWe have to try every combination of city to city travel OR rest in a particular city. R
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe have to try every combination of city to city travel OR rest in a particular city. Recursion or DP can work. We use DP to not re-calculate states and cache.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nIt is important to decide whether forward or backward the transition fucntion makes the most sense. Since days go 0, 1, 2, aka increasing order, I chose to do d + 1 instead of d - 1. \n\n# **The Base case** \nOn the last day, we can either stay in a particular city OR travel to a city that gives us the max points. Hence the equation below:\n>             f[i] = Math.max(stayScore[k - 1][i], Arrays.stream(travelScore[i]).max().getAsInt());\n\n# **The Transition Function**\nFor a Day `d` in a city `c`, we have two choices:\n\n**Stay**: Stay score from day `d` + the profit on day `d + 1` when starting from city `c` \n> int stay = stayScore[d][c] + f[c];\n\n**Travel:** Travel Score to each city `dest` on day `d` + the profit on day `d + 1` when starting from city `dest`\n> travel = Math.max(travel, travelScore[c][dest] + f[dest]);\n\nThe answer for each f[d][c] is the max of stay or travel score on that day.\n\n# **Final Answer**\nThe final answer is the maximum score on day `0`\n\n> Arrays.stream(f).max().getAsInt();\n\n\n\n\n# Complexity\n- Time complexity:\n- For N cities and K days, it is K * N^2. For each city, we are visiting every other city.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n- For N cities and K days, it is K * N. However, since at each day `d`, we only care about `d + 1` day, we can reduce it to O(N). Alternatively, with some more logic, this can be reduced to Min(N, K), but that is too much work for one question, so I skipped it.\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        int[] f = new int[n];\n         // on last day, either stay or travel\n        for (int i = 0; i < n; i++) {\n            f[i] = Math.max(stayScore[k - 1][i], Arrays.stream(travelScore[i]).max().getAsInt());\n        }\n        \n        for (int d = k - 2; d >=0; d--) {    \n            int[] temp = new int[n];\n            for (int c = 0; c < n; c++) {\n                int stay = stayScore[d][c] + f[c];\n                int travel = 0;\n                for (int dest = 0; dest < n; dest++) {\n                    travel = Math.max(travel, travelScore[c][dest] + f[dest]);\n                }\n                temp[c] = Math.max(stay, travel);\n            }            \n            f = temp;\n        }\n        return Arrays.stream(f).max().getAsInt();\n    }\n}\n```
[]