นับวิธีที่จะไปถึงบันไดที่ 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
เพราะเมื่อ for 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