Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.7 kB
4
Indexable
Never
int climbStairs(int n) {
    if (n <= 2) {
        return n;
    }

    return climbStairs(n - 1) + climbStairs(n - 2);
}

/*
Dalam kode tersebut, pendekatan Brute Force digunakan untuk menghitung jumlah cara yang berbeda untuk naik ke puncak tangga dengan n langkah. Ide di balik kode tersebut adalah dengan memecah masalah menjadi submasalah yang lebih kecil dan mencari semua kemungkinan langkah yang dapat diambil pada setiap langkah saat ini.

Pada fungsi climbStairs, kita menggunakan rekursi untuk memecahkan masalah menjadi submasalah yang lebih kecil. Jika n kurang dari atau sama dengan 2, artinya kita hanya memiliki 1 atau 2 langkah, sehingga jumlah cara uniknya sama dengan n itu sendiri.

Jika n lebih besar dari 2, kita menggunakan pendekatan rekursif untuk menghitung jumlah cara unik. Pada setiap langkah saat ini, kita dapat memilih untuk naik 1 langkah atau 2 langkah. Oleh karena itu, jumlah cara unik untuk mencapai langkah saat ini adalah jumlah cara unik untuk mencapai langkah sebelumnya (n-1) ditambah jumlah cara unik untuk mencapai langkah dua langkah sebelumnya (n-2).

Dalam pemanggilan rekursif climbStairs(n - 1) + climbStairs(n - 2), kita secara berulang memanggil fungsi climbStairs dengan langkah yang lebih kecil hingga mencapai basis kasus saat n kurang dari atau sama dengan 2.

Meskipun pendekatan ini sederhana dan mudah dipahami, namun dengan meningkatnya nilai n, jumlah pemanggilan rekursif yang dilakukan akan meningkat secara eksponensial. Hal ini dapat menyebabkan waktu eksekusi yang lama dan memakan banyak sumber daya komputasi. Oleh karena itu, pendekatan ini tidak efisien untuk nilai n yang besar.
*/