Forward-iteration (from day 1 to  k), no helper func and classic brute-force DP with C++
IntuitionGet the best score every city on each day, and the best score is other cities' score previous day plus travel to the city or staying.ApproachJust brute
# Intuition
Get the best score every city on each day, and the best score is other cities' score previous day plus travel to the city or staying.

# Approach
Just brute-force DP, this is the worst problem I’ve seen recently. I even wasted half an hour doubting my intuitive solution.

The time complexity is O(n² * k) because we need to iterate through each day (k), and on each day, we calculate the maximum score for each city (n) if we end up there at the end of the day. The score might be the maximum of traveling from other cities to this city or staying (n).

This might be the most intuitive answer. I don’t know why so many solutions iterate in reverse—it’s so unintuitive. So I made this forward-iteration one.

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

- Space complexity:
This version: O(nk). 
Absolutely, the best solution is to use two arrays of length n and swap them every day. So, the optimal space complexity is actually O(n).

# Code
```cpp []
class Solution {
public:
    int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {
        vector<vector<int>> dp(k+1, vector<int>(n));
        for (int day=0; day<k; day++) {
            int next = day+1;
            for (int city=0; city<n; city++) {
                for (int i=0; i<n; i++) {
                    dp[next][city] = max(dp[next][city], dp[day][i]+travelScore[i][city]);
                }
                dp[next][city] = max(dp[next][city], dp[day][city]+stayScore[day][city]);
            }
        }

        return *max_element(dp[k].begin(), dp[k].end());
    }
};
```
['C++']