Dp solution Using Java,C
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n1. Initialization:\n   
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initialization:\n    - A 2D array dp of size k x n is initialized to store the maximum scores up to each day for each city.\n2. First Day Calculation:\nFor each city on the first day (day 0):\n    - The score is initialized to the score of staying in that city (stayScore[0][city]).\n    - Also check for potential travel from any other city to the current city and updates the score if traveling gives a higher score.\n3. Subsequent Days Calculation:\nFor each day from 1 to k-1:\n    - For each current city, the maximum score is calculated:\n        - Start with the score from the previous day of staying in the same city.\n        - Then, consider traveling from all other cities to the current city and keep track of the maximum possible score.\n# Complexity\n- Time complexity:O(k* n*n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n*k)\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[][] dp = new int[k][n];\n        for (int city = 0; city < n; city++) {\n            dp[0][city] = stayScore[0][city];\n            for (int prevCity = 0; prevCity < n; prevCity++) {\n                if (prevCity != city) {\n                    dp[0][city] = Math.max(dp[0][city], travelScore[prevCity][city]);\n                }\n            }\n        }\n        for (int day = 1; day < k; day++) {\n            for (int currCity = 0; currCity < n; currCity++) {\n                int maxPoints = dp[day - 1][currCity] + stayScore[day][currCity];\n                for (int prevCity = 0; prevCity < n; prevCity++) {\n                    if (prevCity != currCity) {\n                        maxPoints = Math.max(maxPoints, dp[day - 1][prevCity] + travelScore[prevCity][currCity]);\n                    }\n                }\n                dp[day][currCity] = maxPoints;\n            }\n        }\n        int maxScore = Integer.MIN_VALUE;\n        for (int city = 0; city < n; city++) {\n            maxScore = Math.max(maxScore, dp[k - 1][city]);\n        }\n        return maxScore;\n    }\n}\n\n```\n```C []\nint maxScore(int n, int k, int** stayScore, int stayScoreSize, int* stayScoreColSize, int** travelScore, int travelScoreSize, int* travelScoreColSize) {\n    int dp[k][n];\n    for (int city = 0; city < n; city++) {\n        dp[0][city] = stayScore[0][city];\n        for (int prevCity = 0; prevCity < n; prevCity++) {\n            if (prevCity != city) {\n                dp[0][city] = (dp[0][city] > travelScore[prevCity][city]) ? dp[0][city] : travelScore[prevCity][city];\n            }\n        }\n    }\n    for (int day = 1; day < k; day++) {\n        for (int currCity = 0; currCity < n; currCity++) {\n            int maxPoints = dp[day - 1][currCity] + stayScore[day][currCity];\n            for (int prevCity = 0; prevCity < n; prevCity++) {\n                if (prevCity != currCity) {\n                    int travelPoints = dp[day - 1][prevCity] + travelScore[prevCity][currCity];\n                    if (travelPoints > maxPoints) {\n                        maxPoints = travelPoints;\n                    }\n                }\n            }\n            dp[day][currCity] = maxPoints;\n        }\n    }\n    int maxScore = INT_MIN;\n    for (int city = 0; city < n; city++) {\n        if (dp[k - 1][city] > maxScore) {\n            maxScore = dp[k - 1][city];\n        }\n    }\n    return maxScore;\n}\n```
[]