Leetcode 3179. Find the N-th Value After K Seconds
- Leetcode 3179. Find the N-th Value After K Seconds
- 1. 解题思路
- 2. 代码实现
- 题目链接：3179. Find the N-th Value After K Seconds
1. 解题思路
这一题的话还是一个动态规划的问题，核心递推关系式为：
dp(n, k) = dp(n-1, k) + dp(n, k)
我们用cache实现一下即可。
2. 代码实现
给出python代码实现如下：
MOD = 10**9+7@lru_cache(None)
def fn(n, k):if n == 1 or k == 0:return 1return (fn(n-1, k) + fn(n, k-1)) % MODclass Solution:def valueAfterKSeconds(self, n: int, k: int) -> int:return fn(n, k)
提交代码评测得到：耗时787ms，占用内存174.6MB。