（字节面试题）青蛙跳台变形（一次 k 阶台阶）

admin管理员组

文章数量:823383

（字节面试题）青蛙跳台变形（一次 k 阶台阶）

你一开始在底部，每次可以向上迈最多K级台阶（最少1级），问到达第N级台阶有多少种不同方式，一个学姐在字节面试面到的题目，一次 可以 迈 k 阶台阶，普通的青蛙跳台是迈 1 或者 2，现在是 1 - k 都有可能，所以，依旧使用数组进行求解：范围在 i - k 之间的数都加上，动态转移方程：

dp[n] = dp[n - 1] + dp[n - 2] + ..... + dp[n - k]

解：

import java.util.*;
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int k = sc.nextInt();int[] dp = new int[n + 1];dp[0] = 1;for (int i = 1; i <= n; i++) {for (int j = 1; j <= k && i - j >= 0; j++) {dp[i] += dp[i - j];}}System.out.println(dp[n]);}
}

发现上面的代码是可以优化的，因为求 i - k 范围内的和，完全可以使用找规律代码：
当 n 小于 k 的时候，

dp[n] = dp[n - 1] + dp[n - 2].....+ dp[0]
dp[n -1] = dp[n - 2] + ..... + dp[0];
所以 dp[n] = 2 fp[n - 1];

当 n 大于 k 的时候，

f[n] = f[n-1] + f[n-2] + f[n-3] + ... + f[n-m]f[n-1] = f[n-2] + f[n-3] + ... + f[n-1-m]f[n] = 2*f[n-1] - f[n-1-m]

所以直接循环体：

package company;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int k = sc.nextInt();int[] dp = new int[n + 1];int[] sum = new int[n + 1];dp[0] = 1;for (int i = 1; i <= n; i++) {if (i <= k) {dp[i] = (int) Math.pow(2.0, i - 1.0);} else {dp[i] = 2 * dp[i - 1] - dp[i - 1 - k];}}System.out.println(dp[n]);}
}

本文标签： （字节面试题）青蛙跳台变形（一次 k 阶台阶）