Java DP|| N^2*K T.C || SC O(N)
\nclass Solution {\n    public int maxScore(int N, int K, int[][] stayScore, int[][] travelScore) {\n        int best = 0;\n        int[][] dp = new int[2][N + 
```\nclass Solution {\n    public int maxScore(int N, int K, int[][] stayScore, int[][] travelScore) {\n        int best = 0;\n        int[][] dp = new int[2][N + 1];\n        for (int k = K; k >= 0; k--) {\n            for (int i = N; i >= 0; i--) {\n                if (i == N || k == K) dp[k & 1][i] = 0;\n                else {\n                    int stay = stayScore[k][i] + dp[(k + 1) & 1][i];\n                    int leave = 0;\n                    for (int j = 0; j < N; j++) {\n                        leave = Math.max(leave, travelScore[i][j] + dp[(k + 1) & 1][j]);\n                    }\n                    dp[k & 1][i] = Math.max(stay, leave);\n                }\n                if (k == 0) best = Math.max(best, dp[k & 1][i]);\n            }\n        }\n        return best;\n    }\n}\n```
[]