Hitung cara untuk mencapai tangga ke-4 menggunakan langkah 1, 2, atau 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]);
    }

Output saya adalah 6 , tetapi sebenarnya seharusnya 7.

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

jadi total jawabannya harusnya 7, di mana saya salah??


java dynamic algorithm
person LoganPaul    schedule 20.10.2019    source sumber
comment
karena ketika i=3 sedang berjalan, ia menambahkan arr[2]+arr[1]+arr[0] dan Anda belum mendefinisikan arr[0] sehingga memperbarui arr[3] sebagai 3. ketika dijalankan arr[4]=3+2+1 =6   -  person Ayushi Keshri    schedule 20.10.2019

Jawaban (1)


arrow_upward
1
arrow_downward

Perulangan for Anda dimulai dengan i = 3, tetapi Anda sudah mengisi res[3]. Hal ini tidak menjadi masalah jika jumlah cara untuk mencapai 3 sama dengan nilai hardcode Anda arr[3] = 4;, namun tidak.

Memang benar, Anda belum pernah menyetel res[0] ke 1, dan oleh karena itu, res[3] = res[2] + res[1] + res[0] akan dihitung sebagai 3, bukan 4.

Anda selanjutnya mengembalikan res[3] alih-alih res[n], dan Anda harus menginisialisasi array dengan panjang n+1.

Perbaikan terkecil adalah menyetel res[0] ke 1 juga:

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