java - 使用步骤 1、2 或 3 计算到达第 4 级楼梯的方法

Question

public static void main(String[] args) {
        int n = 46;
        int [] arr = new int[n];
        arr[1]=1;
        arr[2]= 2;
        arr[3]=4;
        for(int i=3;i<n;i++){
            arr[i]= arr[i-1]+arr[i-2]+arr[i-3];
        }
        System.out.println(arr[3]);
    }

我的输出是 6 ，但实际上应该是 7。

arr[1] = 1 way.
arr[2] = 1,1 or 2 
arr[3] = 1,1,1 ; 2,1 ; 1,2 ; 3 

所以总的来说答案应该是 7，我哪里错了？？

标签： javaalgorithmdynamic

Answer 1

您的for循环以 开头i = 3，但您已经填写了res[3]。如果到达方式的数量与3硬编码值相同，这不是问题arr[3] = 4;，但事实并非如此。

实际上，您从未设置res[0]为1，因此，它将计算res[3] = res[2] + res[1] + res[0]为3，而不是4。

您还返回res[3]而不是res[n]，并且您应该初始化一个长度数组n+1。

因此，最小的修复也是设置res[0]为1：

public static void main(String[] args) {
    int n = 46;
    int [] arr = new int[n+1];
    arr[0] = 1;
    arr[1] = 1;
    arr[2] = 2;
    arr[3] = 4;
    for(int i = 3; i < n; i++){
        arr[i]= arr[i-1]+arr[i-2]+arr[i-3];
    }
    System.out.println(arr[n]);
}