（字节面试题）青蛙跳台变形（一次 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 com.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]);
    }
}