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 1
return (fn(n-1, k) + fn(n, k-1)) % MOD
class Solution:
def valueAfterKSeconds(self, n: int, k: int) -> int:
return fn(n, k)
提交代码评测得到：耗时787ms，占用内存174.6MB。