跳跃训练
难度:
标签:
题目描述
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`两个变量而不是维护整个数组?
▷🦆
在算法中,为何选择在最后返回结果时才进行模1e9+7操作而不是每次迭代时都取模?
▷