难度: Easy
今天的有氧运动训练内容是在一个长条形的平台上跳跃。平台有 num 个小格子，每次可以选择跳 一个格子 或者 两个格子。请返回在训练过程中，学员们共有多少种不同的跳跃方式。
结果可能过大，因此结果需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2 输出：2
示例 2：
输入：n = 5 输出：8
提示：
0 <= n <= 100注意：本题与主站 70 题相同：https://leetcode-cn.com/problems/climbing-stairs/
运行时间: 36 ms
内存: 13.1 MB
class Solution:
def numWays(self, n: int) -> int:
a, b = 1, 1
for _ in range(n):
a, b = b, a+b
return a % 1000000007
该题解使用动态规划的思想来解决问题。定义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)
class Solution:
def numWays(self, n: int) -> int:
# 初始化两个变量，a为dp[i-2]，b为dp[i-1]，初始时都设为1，即dp[0]和dp[1]
a, b = 1, 1
# 循环n次，计算从dp[1]到dp[n]
for _ in range(n):
# 更新dp[i]。新的b为dp[i]，即a+b；a更新为旧的b
a, b = b, a + b
# 返回结果需取模1e9+7
return a % 1000000007
动态规划适合解决具有重叠子问题和最优子结构的问题，跳跃方式数问题正好符合这些特点。每个状态（即达到每个格子的方式数）都可以由前面的状态递推得来，这种问题的每个状态是后续状态的基础，形成了重叠子问题。而动态规划可以将每个状态的解存储下来，避免重复计算，从而提高效率。使用其他算法如递归可能会导致大量的重复计算，效率较低。
在这个问题中，`a`和`b`的初始值都设为1代表了最基础的几种跳跃情况。`a`代表dp[0]，即在起点0的位置时的跳跃方式数，自然是1种（即不跳）。`b`代表dp[1]，即到达第1个格子的跳跃方式数，也是1种（从起点直接跳1格到达）。这两个值作为递推的基础，用于计算后续每个位置的跳跃方式数。
这是一种空间优化措施。在计算当前位置的跳跃方式数时，只需要知道前两个位置的跳跃方式数，因此没有必要维护一个完整的dp数组来存储所有位置的跳跃方式数。通过仅使用两个变量`a`和`b`来存储必要的前两个状态，可以大幅减少算法的空间复杂度，从O(n)减少到O(1)，而不影响计算的正确性或效率。
理论上，每次迭代后进行模操作可以保证数值不会过大，避免溢出，并且最终结果仍然正确。但在实际应用中，由于Python的整数类型是动态的，可以处理非常大的数，因此即使在迭代过程中数值增大，也不会导致溢出。因此，可以选择在最终结果计算完成后进行一次模操作，以减少计算量。不过，如果在其他编程语言或环境中，可能需要在每次迭代时都进行模操作，以确保不会溢出。