Java 中查找 K 秒后第 N 个值的

给定两个整数 n 和 k。我们最初有一个包含 n 个整数的数组 an，其中 0 <= i <= n - 1，使得 a[i] = 1。每秒，我们同时更新每个元素，使其等于它之前所有元素之和加上它本身。k 秒后，返回 a[n - 1] 的值。

示例 1

输入

int n = 4

int k = 5

输出

k 秒后的值为 56。

解释

由于给定的 n 值为 4，因此将数组元素初始化为 [1, 1, 1, 1]。我们重复 k 次（在本例中为五次）。根据前一状态元素的累积总和，我们在每次迭代中更新数组。

示例 2

输入

int n = 5

int k = 3

输出

k 秒后的值为 35。

解释

由于给定的 n 值为 5，因此将数组元素初始化为 [1, 1, 1, 1, 1]。我们重复 k 次（在本例中为三次）。根据前一状态元素的累积总和，我们在每次迭代中更新数组。

方法：使用动态规划

问题是如何以特定方式在几秒钟内更新数组。数组中每个元素的值都会更改为等于其所有前驱元素之和再加上它本身。此过程类似于创建累积和数组，其中每次迭代都会导致每个成员逐渐累积值。任务是在这些修改后找到数组最后一个元素的值。

算法

步骤 1：初始化一个包含 ? 个元素的数组，并将每个元素设置为 1。

步骤 2：对于 1 到 ? 之间的每一秒。

步骤 2.1：从数组的第二个条目开始，通过添加前面元素的值来更新每个后续元素。

步骤 2.2：到目前为止的累积总和会增加。

步骤 3：为了避免过载并控制值，请使用模运算。

步骤 4：? 秒后，返回结果；数组的最后一个条目是所需的值。

实施

文件名： NValueKsecsAfter.java

输出

 
The value after 5 seconds for the given value 4 is: 56   

复杂度分析

上述代码的时间复杂度为 O(n×k)，其中 k 是秒数，n 是元素数量。其空间复杂度为 O(n)。