摘要: 动态规划入门题。
题目 一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。 __示例 1:
输入: n = 2输出: 2
示例 2:
输入: n = 7输出: 21
示例 3:
输入: n = 0输出: 1
提示:
动态规划 注意数值溢出,可以每一步计算取模。正确性证明参见:剑指Offer 10-I. 斐波那契数列 还有一点就是注意特判 n == 0
的情况。 本题起始位置为0层。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : const int64_t _mod = 1e9 + 7 ; int numWays (int n) { int64_t dp[n + 10 ]; dp[0 ] = 1 , dp[1 ] = 1 ; for (int i = 2 ; i <= n; i++) { dp[i] = dp[i - 2 ] + dp[i - 1 ]; dp[i] %= _mod; } return dp[n]; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { final int mod = 1000000007 ; public int numWays (int n) { int [] dp = new int [110 ]; dp[0 ] = 1 ; dp[1 ] = 1 ; for (int i = 2 ; i <= n; i++) { dp[i] = dp[i - 2 ] + dp[i - 1 ]; dp[i] %= mod; } return dp[n]; } }
空间复杂度优化的动态规划 可以用三个变量滚动更新,代替数组。 核心是一共计算$n - 1$次,每次计算 c
的值,动态更新 a
, b
。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : const int64_t mod = 1e9 + 7 ; int numWays (int n) { if (!n) return 1 ; int64_t a, b, c; c = b = a = 1 ; while (--n) { c = a + b; c %= mod; a = b, b = c; } return c; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { final int mod = 1000000007 ; public int numWays (int n) { if (n == 0 ) return 1 ; int a = 1 ; int b = 1 ; int c = 1 ; for (int i = 0 ; i < n - 1 ; i++) { c = a + b; c %= mod; a = b; b = c; } return c; } }