leetcode
leetcode 2551 ~ 2600
跳跃训练

跳跃训练

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 36 ms, 内存: 13.1 MB


/*
 * 问题描述:给定一个n个格子的长条形平台,
 * 每次可以选择跳一个格子或者两个格子,问有多少种不同的跳跃方式。
 * 思路:使用Java Stream进行流式编程。
 * 首先通过Stream.iterate生成一个无穷序列,
 * 每次计算时更新状态。
 * 然后使用limit限制只计算n次,最后获取最终结果。
 */
import java.util.stream.Stream;

public class SolutionStream {
    public int numWays(int n) {
        int MOD = 1000000007;
        return Stream.iterate(new int[]{1, 1}, arr -> new int[]{arr[1], (arr[0] + arr[1]) % MOD})
                     .limit(n + 1)
                     .mapToInt(arr -> arr[0])
                     .reduce((first, second) -> second)
                     .orElse(1);
    }
}

解释

方法:

该题解使用动态规划的思想来解决问题。定义dp[i]为到达第i个格子的跳跃方式数。从题目条件可知,到达第i个格子有两种方式,一种是从第i-1个格子跳一个格子过来,另一种是从第i-2个格子跳两个格子过来。因此,状态转移方程为dp[i] = dp[i-1] + dp[i-2]。为了优化空间复杂度,使用两个变量a和b分别存储dp[i-2]和dp[i-1]的值,每次迭代计算新的dp[i]并更新这两个变量。最终dp[n]即为答案,由于结果要求模1e9+7,所以返回时进行取模操作。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在求解跳跃方式数时使用动态规划而不是其它算法?
动态规划适合解决具有重叠子问题和最优子结构的问题,跳跃方式数问题正好符合这些特点。每个状态(即达到每个格子的方式数)都可以由前面的状态递推得来,这种问题的每个状态是后续状态的基础,形成了重叠子问题。而动态规划可以将每个状态的解存储下来,避免重复计算,从而提高效率。使用其他算法如递归可能会导致大量的重复计算,效率较低。
🦆
在动态规划中,初始状态`a`和`b`都设为1代表了哪些情况?
在这个问题中,`a`和`b`的初始值都设为1代表了最基础的几种跳跃情况。`a`代表dp[0],即在起点0的位置时的跳跃方式数,自然是1种(即不跳)。`b`代表dp[1],即到达第1个格子的跳跃方式数,也是1种(从起点直接跳1格到达)。这两个值作为递推的基础,用于计算后续每个位置的跳跃方式数。
🦆
为什么在迭代过程中,只需要更新`a`和`b`两个变量而不是维护整个数组?
这是一种空间优化措施。在计算当前位置的跳跃方式数时,只需要知道前两个位置的跳跃方式数,因此没有必要维护一个完整的dp数组来存储所有位置的跳跃方式数。通过仅使用两个变量`a`和`b`来存储必要的前两个状态,可以大幅减少算法的空间复杂度,从O(n)减少到O(1),而不影响计算的正确性或效率。
🦆
在算法中,为何选择在最后返回结果时才进行模1e9+7操作而不是每次迭代时都取模?
理论上,每次迭代后进行模操作可以保证数值不会过大,避免溢出,并且最终结果仍然正确。但在实际应用中,由于Python的整数类型是动态的,可以处理非常大的数,因此即使在迭代过程中数值增大,也不会导致溢出。因此,可以选择在最终结果计算完成后进行一次模操作,以减少计算量。不过,如果在其他编程语言或环境中,可能需要在每次迭代时都进行模操作,以确保不会溢出。

相关问题