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

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


java dynamic algorithm
person LoganPaul    schedule 20.10.2019    source источник
comment
потому что когда для i=3 работает, он добавляет arr[2]+arr[1]+arr[0], и вы не определили arr[0], поэтому он обновляет arr[3] как 3. когда он собирается для обр[4]=3+2+1 =6   -  person Ayushi Keshri    schedule 20.10.2019

Ответы (1)


arrow_upward
1
arrow_downward

Ваш цикл 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]);
}
person Willem Van Onsem    schedule 20.10.2019