[Java] Explained Quickest DP + Memo Solution
Intuition2D Top-Down Memoization.The Memoization table stores the max value if we're at city i and it's the kth day. Thus, it stores the reslt of traveling to t
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
2D Top-Down Memoization.

The Memoization table stores the max value if we're at city i and it's the kth day. Thus, it stores the reslt of traveling to the (k + 1)th city on the kth day. This memoization table makes sure each calculation only occurs once (allowing for polynomial rather than exponential time complexity).

# Approach
<!-- Describe your approach to solving the problem. -->
Use recursion to population the memoization table, starting from every city on the 0th day. 
For each day for every city, we have the option of
1. staying at the current city (using stayScore)
2. moving to another city (using travelScore)
So simply add that to the recursive result of each action.

On the kth day, there is no more traveling, so return 0 as the base case. 
Return the max of the first row of the table i.e. the max value of starting at each city at day 0.

# Complexity
- Time complexity: O(k * n^2)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

At each day, for every city, we check all possible cities we can go to. That is n checks for each day for each city, memoization makes sure this only happens once (no repeated calculations) -> 1 * n * n * k
- Space complexity: O(n * k)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
Space for the memoization table.

# Code
```java []
class Solution { // 20 minutes after DP refresher
    // memoization table stores the max value if we're at city i and it's the kth day, so the result of traveling to (k+1)th
    // On kth day, no more traveling, base case k should return 0 (no points to be made), values for 0 to k-1 should be populated
    int[][] memo;

    public int maxScore(int n, int k, int[][] stayScore, int[][] travelScore) {
        // Initializes memo table with all -1s
        memo = new int[k][n];
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < n; j++) {
                memo[i][j] = -1;
            }
        }

        // Start from every city
        int max = -1;
        for (int i = 0; i < n; i++) {
            maxScoreRec(n, k, i, 0, stayScore, travelScore);
            max = Math.max(max, memo[0][i]);
        }
        return max;
    }

    // Returns maxScore if our current city is city and we're on day day (traveling to day + 1)
    // Also populates memo[day][city], if not already populated
    public int maxScoreRec(int n, int k, int city, int day, int[][] stayScore, int[][] travelScore) {
        if (day >= k) {
            return 0;
        }

        if (memo[day][city] != -1) {
            return memo[day][city];
        }

        // Result of staying at current city on current day
        int max = stayScore[day][city] + maxScoreRec(n, k, city, day + 1, stayScore, travelScore);
        // Result of traveling to all other cities on current day from current city
        for (int nextCity = 0; nextCity < n; nextCity++) {
            if (nextCity == city) {
                continue; // already did this case using the stayScore
            }
            int temp = travelScore[city][nextCity] + maxScoreRec(n, k, nextCity, day + 1, stayScore, travelScore);
            max = Math.max(max, temp);
        }

        // Populates memo table so this calculation only happens once
        memo[day][city] = max;
        return max;
    }
}
```
['Java']