Easy,Small,Well Explained, Beginner Friendly Solution , Recursive (memoization) , Top-down DP
ApproachLET'S BECOME DORA THE EXPLORER - TOGETHER 🎒🏕Let's divide the problem into multiple parts:
As mentioned we can start from any position means our start ca
# Approach


---
**LET'S BECOME DORA THE EXPLORER - TOGETHER** 🎒🏕

---



Let's divide the problem into multiple parts:

1. As mentioned we can start from any position means our start can be any node:
```
 Therefore we have to use loop and check the value got from every other node and 
 max should be our ans.

```
2. **Our DP logic** : In normal english **Either I will stay or I will travel.**
```
In case of stay: 
- use the stay_value of current day & node where we are staying 
    i.e - stayScore[day][node]
- increase the day by 1 since we have stayed at same node for 1 day extra.
- so our total will be (expression): 
      
               ----------------------------------------------
               stay  =  stayScore[day][node]+dp(day+1,node)
               ----------------------------------------------


In case of travel:
- Since it's mentioned that each node is reachable to other nodes.
- We would love to travel every other node and 
  check which can give us the maximum value.
- Again if we are travelling means we are using 1 day extra and some travel cost is assosiated with it.
- source & destination can't be same.
- so our travel total will be for 1 destination (expression):
    
------------------------------------------------------------------------------
    travel  =  travelScore[source_node][destination_node] + dp(day+1,node)
-----------------------------------------------------------------------------

- for all destination :
     
        for destination_node in range(total_nodes):
                if(destination_node != source_node):
                    travel = max(travel, travelScore[source_node][destination_node] + dp(day+1,node))

```

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

- Space complexity: $$O(n*k)$$

```
WARNING: MEMOIZATION using variable is giving TLE. 
Therefore I have used the cache but I have posted the solution with memo too. 
```

# Code


```python3 [WITH CACHE]
import sys
sys.setrecursionlimit(10**8)

class Solution:
    def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:
        @lru_cache(maxsize=None)
        def dpAns(currK,currN):
            if(currK == k):
                return 0
            #stay
            ans = stayScore[currK][currN]+dpAns(currK+1,currN) 
            # move
            for j in range(n):
                if(j != currN):
                    ans = max(ans, travelScore[currN][j]+dpAns(currK+1,j))
            return ans
    
        ans = 0
        dp = {}
        for i in range(n):
            ans = max(ans, dpAns(0,i))
        return ans
```

```python3 [WITHOUT CACHE]

    def dpAns(self,dp,currK,currN,stayScore,travelScore,n,k):
        if(currK == k):
            return 0
        if((currN, currK) in dp):
            return dp[(currN,currK)]
        #stay
        dp[(currN,currK)] = stayScore[currK][currN]+self.dpAns(dp,currK+1,currN,stayScore,travelScore,n,k) 
        # move
        for j in range(n):
            if(j != currN):
                dp[(currN,currK)] = max(dp[(currN,currK)], travelScore[currN][j]+self.dpAns(dp,currK+1,j,stayScore,travelScore,n,k))
        return dp[(currN,currK)]
```
['Dynamic Programming', 'Recursion', 'Matrix', 'Python3']