Easy Dp memozation solution
Intuition\n1. Use all posssible ways to find max\n\n\n# Overall Calculation (maxScore function):\n\n1. The main function initializes the dp table (for memoizati
# Intuition\n1. Use all posssible ways to find max\n\n\n# Overall Calculation (maxScore function):\n\n1. The main function initializes the dp table (for memoization) and iterates over all possible starting cities.\n2. For each city, it calculates the maximum possible score starting from day 0 and updates ans with the highest score encountered.\n\n# Recurrence Relation (findans function):\n1. Base Case: If day == k (end of the time period), return 0 since no more score can be accumulated.\n2. Memoization Check: If the score for the current city and day is already computed (dp[curr][day] != -1), return that stored result to avoid redundant calculations.\n3. Stay Option: Calculate the score if staying in the current city by adding the stayScore for that day and city, plus recursively calling findans for the next day in the same city.\n4. Travel Option: Try traveling to each other city. For each possible destination i, add the travel score and recursively calculate the score for the next day in city i. Store the maximum score possible by traveling to any other city.\n# Complexity\n- Time complexity:\nO(N*K)\n\n- Space complexity:\nO(N*K)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int findans(int day, int curr, int k,vector<vector<int>>& stayscore, vector<vector<int>>& travelscore,int n,vector<vector<int>>&dp){\n        if(day==k){\n            return 0;\n        }\n\n        if(dp[curr][day]!=-1){\n            return dp[curr][day];\n        }\n        //stay on curr city\n        int x=stayscore[day][curr]+findans(day+1,curr,k,stayscore,travelscore,n,dp);\n\n        //trvale to other city\n        int y=0;\n        for(int i=0;i<n;i++){\n             if(i!=curr){\n                y=max(y,travelscore[curr][i]+findans(day+1,i,k,stayscore,travelscore,n,dp));\n             }\n        }\n\n        return dp[curr][day]=max(x,y);\n    }\n    int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {\n        \n        int ans=0;\n        vector<vector<int>>dp(n+1,vector<int>(k+1,-1));\n        for(int i=0;i<n;i++){\n            ans=max(ans,findans(0,i,k,stayScore,travelScore,n,dp));\n        }\n\n        return ans;\n    }\n};\n```\n```java []\nclass Solution {\n    public int findans(int day, int curr, int k, int[][] stayScore, int[][] travelScore, int n, int[][] dp) {\n        if (day == k) {\n            return 0;\n        }\n\n        if (dp[curr][day] != -1) {\n            return dp[curr][day];\n        }\n        \n        // Stay in current city\n        int x = stayScore[day][curr] + findans(day + 1, curr, k, stayScore, travelScore, n, dp);\n\n        // Travel to another city\n        int y = 0;\n        for (int i = 0; i < n; i++) {\n            if (i != curr) {\n                y = Math.max(y, travelScore[curr][i] + findans(day + 1, i, k, stayScore, travelScore, n, dp));\n            }\n        }\n\n        return dp[curr][day] = Math.max(x, y);\n    }\n\n    public int maxScore(int n, int k, int[][] stayScore, int[][] travelScore) {\n        int ans = 0;\n        int[][] dp = new int[n + 1][k + 1];\n        for (int i = 0; i <= n; i++) {\n            Arrays.fill(dp[i], -1);\n        }\n\n        for (int i = 0; i < n; i++) {\n            ans = Math.max(ans, findans(0, i, k, stayScore, travelScore, n, dp));\n        }\n\n        return ans;\n    }\n}\n\n```\n```python []\nclass Solution:\n    def findans(self, day, curr, k, stayScore, travelScore, n, dp):\n        if day == k:\n            return 0\n\n        if dp[curr][day] != -1:\n            return dp[curr][day]\n\n        # Stay in current city\n        x = stayScore[day][curr] + self.findans(day + 1, curr, k, stayScore, travelScore, n, dp)\n\n        # Travel to another city\n        y = 0\n        for i in range(n):\n            if i != curr:\n                y = max(y, travelScore[curr][i] + self.findans(day + 1, i, k, stayScore, travelScore, n, dp))\n\n        dp[curr][day] = max(x, y)\n        return dp[curr][day]\n\n    def maxScore(self, n, k, stayScore, travelScore):\n        ans = 0\n        dp = [[-1 for _ in range(k + 1)] for _ in range(n + 1)]\n        for i in range(n):\n            ans = max(ans, self.findans(0, i, k, stayScore, travelScore, n, dp))\n        \n        return ans\n\n```\n```javascript []\nclass Solution {\n    findans(day, curr, k, stayScore, travelScore, n, dp) {\n        if (day === k) {\n            return 0;\n        }\n\n        if (dp[curr][day] !== -1) {\n            return dp[curr][day];\n        }\n\n        // Stay in current city\n        let x = stayScore[day][curr] + this.findans(day + 1, curr, k, stayScore, travelScore, n, dp);\n\n        // Travel to another city\n        let y = 0;\n        for (let i = 0; i < n; i++) {\n            if (i !== curr) {\n                y = Math.max(y, travelScore[curr][i] + this.findans(day + 1, i, k, stayScore, travelScore, n, dp));\n            }\n        }\n\n        dp[curr][day] = Math.max(x, y);\n        return dp[curr][day];\n    }\n\n    maxScore(n, k, stayScore, travelScore) {\n        let ans = 0;\n        let dp = Array.from({ length: n + 1 }, () => Array(k + 1).fill(-1));\n        \n        for (let i = 0; i < n; i++) {\n            ans = Math.max(ans, this.findans(0, i, k, stayScore, travelScore, n, dp));\n        }\n\n        return ans;\n    }\n}\n\n```\n![c2d27b08-ffbe-4bc6-8b29-5fc4d8effd5f_1723775276.9029489.jpeg](https://assets.leetcode.com/users/images/e4a3b8b1-3e9b-4868-bdb9-82b76bd98606_1730015621.7238731.jpeg)\n
[]