23.04.15 Today’s Leetcode

2218. Maximum Value of K Coins From Piles

TLE at 4/122

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:

        n = len(piles)
        index = [0] * n
        res = 0

        def dfs(cur, count):
            if count == 0:
                nonlocal res
                res = max(res, cur)
                return
            for i in range(n):
                if index[i] >= len(piles[i]):
                    continue
                index[i] += 1
                dfs(cur + piles[i][index[i] - 1], count - 1)
                index[i] -= 1
        
        dfs(0, k)
        return res

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        
        @functools.lru_cache(None)
        def func(i, k):
            if k == 0 or i == len(piles): 
                return 0
            res, cur = func(i + 1, k), 0
            for j in range(min(len(piles[i]), k)):
                cur += piles[i][j]
                res = max(res, cur + func(i + 1, k - j - 1))
            return res
        
        return func(0, k)

365. Water and Jug Problem (medium)

from math import gcd

class Solution:
  def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:
    # Base case: target capacity is 0
    if targetCapacity == 0:
        return True
    # If the sum of jug capacities is less than target capacity, it's impossible
    if jug1Capacity + jug2Capacity < targetCapacity:
        return False
    
    # Check if target capacity is divisible by the greatest common divisor of jug capacities
    return targetCapacity % gcd(jug1Capacity, jug2Capacity) == 0