Подсчитайте, как добраться до 4-й ступени, используя шаги 1, 2 или 3

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где я ошибаюсь ??

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[<b>n+1</b>];
    <b>arr[0] = 1;</b>
    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[<b>n</b>]);
}