丢棋子问题

class Solution:
    def solve(self , n: int, k: int) -> int:
        # write code here
        memo={}
        def dp(n,k):
            if k==1:return n
            if n==0:return 0
            if (n,k) in memo.keys():
                return memo[(n,k)]
            res=float('Inf')
            left=1
            right=n
            while left<=right:
                mid=(left+right)//2
                broken=dp(mid-1,k-1)
                no_broken=dp(n-mid,k)
                if broken>no_broken:
                    res=min(res,broken+1)
                    right=mid-1
                else:
                    res=min(res,no_broken+1)
                    left=mid+1
            memo[(n,k)]=res
            return res
        return dp(n,k)

from functools import lru_cache
class Solution:
    def solve(self, n, k):
        @lru_cache()
        def f(i, n):
            if i == 1:return n
            if n == 1:return 1
            return f(i, n-1) + f(i-1, n-1) + 1
        res = 1
        while f(k, res) < n:
            res += 1
        return res