Medium

题目描述

给你两个整数 n 和 k。

初始时，你有一个长度为 n 的整数数组 a，对于所有 0 <= i <= n - 1，都有 a[i] = 1。每一秒钟后，你会同时更新每个元素，使其等于该元素及其前面所有元素的和。例如，一秒钟后，a[0] 保持不变，a[1] 变为 a[0] + a[1]，a[2] 变为 a[0] + a[1] + a[2]，依此类推。

返回 k 秒后 a[n - 1] 的值。

由于答案可能很大，请返回答案对 10^9 + 7 取模的结果。

示例 1：

输入：n = 4, k = 5
输出：56
解释：
秒数    状态
0       [1,1,1,1]
1       [1,2,3,4]
2       [1,3,6,10]
3       [1,4,10,20]
4       [1,5,15,35]
5       [1,6,21,56]

示例 2：

输入：n = 5, k = 3
输出：35
解释：
秒数    状态
0       [1,1,1,1,1]
1       [1,2,3,4,5]
2       [1,3,6,10,15]
3       [1,4,10,20,35]

约束条件：

  • 1 <= n, k <= 1000

提示：

  • 计算数组 nums 的前缀和数组，重复 k 次。

解题思路

思路分析

这道题的核心是理解数组的更新规律。每一秒钟，数组中的每个元素都会更新为从数组开头到该位置所有元素的和，这实际上就是计算前缀和。

基本思路：模拟过程 最直观的方法是按照题目描述直接模拟 k 次前缀和计算过程。每一轮都遍历数组，将每个位置更新为从开头到当前位置的累积和。

优化思路：组合数学 深入分析可以发现，这个过程与组合数学中的杨辉三角有密切关系。经过 k 轮更新后，位置 i 的值实际上等于组合数 C(k+i, i)。但由于需要取模运算且涉及大数计算，实现较为复杂。

推荐解法：直接模拟 考虑到约束条件 n, k ≤ 1000，直接模拟的时间复杂度 O(nk) 完全可以接受，且实现简单不易出错。我们只需要 k 轮循环，每轮计算一次前缀和即可。

需要注意的是要在每次加法操作后进行取模，防止整数溢出。

代码实现

class Solution {
public:
    int valueAfterKSeconds(int n, int k) {
        vector<long long> a(n, 1);
        const int MOD = 1e9 + 7;
        
        for (int second = 0; second < k; second++) {
            for (int i = 1; i < n; i++) {
                a[i] = (a[i] + a[i-1]) % MOD;
            }
        }
        
        return a[n-1];
    }
};

class Solution:
    def valueAfterKSeconds(self, n: int, k: int) -> int:
        a = [1] * n
        MOD = 10**9 + 7
        
        for _ in range(k):
            for i in range(1, n):
                a[i] = (a[i] + a[i-1]) % MOD
        
        return a[n-1]

public class Solution {
    public int ValueAfterKSeconds(int n, int k) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = 1;
        }
        
        const int MOD = 1000000007;
        
        for (int second = 0; second < k; second++) {
            for (int i = 1; i < n; i++) {
                a[i] = (a[i] + a[i-1]) % MOD;
            }
        }
        
        return (int)a[n-1];
    }
}

var valueAfterKSeconds = function(n, k) {
    let a = new Array(n).fill(1);
    const MOD = 1e9 + 7;
    
    for (let second = 0; second < k; second++) {
        for (let i = 1; i < n; i++) {
            a[i] = (a[i] + a[i-1]) % MOD;
        }
    }
    
    return a[n-1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n × k)
空间复杂度O(n)

相关题目