Simple Java Solution
Code\njava []\nclass Solution {\n    int result=0;\n    int dp[][]=new int[201][201];\n    public int Solve(int k, int[][] stayScore, int[][] travelScore,int da
# Code\n```java []\nclass Solution {\n    int result=0;\n    int dp[][]=new int[201][201];\n    public int Solve(int k, int[][] stayScore, int[][] travelScore,int day,int curCity)\n    {\n        if(day==k)\n        {\n            return 0;\n        }\n        if(dp[day][curCity]!=-1)\n        {\n            return dp[day][curCity];\n        }\n        int max=0;\n        if(day==0)\n        {\n              for(int i=0;i<stayScore[0].length;i++)\n              {\n              max=Math.max(max,stayScore[0][i]+Solve(k,stayScore,travelScore,day+1,i));\n              }\n              for(int i=0;i<travelScore.length;i++)\n              {\n                for(int j=0;j<travelScore[0].length;j++)\n                {\n                    if(travelScore[i][j]!=0)\n                    {\n                        max=Math.max(max,travelScore[i][j]+Solve(k,stayScore,travelScore,day+1,j));\n                    }\n                }\n              }\n        }\n        else\n        {\n            max=Math.max(max,stayScore[day][curCity]+Solve(k,stayScore,travelScore,day+1,curCity));\n            for(int j=0;j<travelScore[0].length;j++)\n                {\n                    if(j!=curCity)\n                    {\n                        max=Math.max(max,travelScore[curCity][j]+Solve(k,stayScore,travelScore,day+1,j));\n                    }\n                }\n        }\n\n        return dp[day][curCity]=max;\n\n    }\n    public int maxScore(int n, int k, int[][] stayScore, int[][] travelScore) {\n        for(int i=0;i<dp.length;i++)\n        {\n            Arrays.fill(dp[i],-1);\n        }\n        return Solve(k,stayScore,travelScore,0,0);\n    }\n}\n```
[]