回溯N樓梯問題得到0個案例Java-有解無憂

N個樓梯問題是計算到達頂部的不同方式的數量。每次您可以爬 1 或 2 級臺階。例如，如果輸入為 3，則所需的輸出為 3 (1 1 1,1 2,??2 1)。

我正在學習 Java 中的回溯，所以我想在這個問題中實作它，盡管 DP 在這種情況下會更好地作業。如果我很好地理解回溯，我將其視為一種練習，但顯然不是。我被卡住了，因為我的演算法為我提供0了每種情況的輸出。下面是我的代碼：

    public int climbStairs(int n) {
        int cnt=0,k=0;
        climb(cnt,k,n);
        return cnt;
    }
    public void climb(int cnt, int k, int n){
        if(k==n){
            cnt  ;
            return; 
        }
        for(int i=1;i<3;  i){
            if(k<n){
                k =i;
                climb(cnt,k,n);
                k-=i;
            }
        }
    }

你能幫我弄清楚我的代碼有什么問題嗎？我嘗試除錯它，我注意到每次它回傳時，cnt都會自動更改為0，但我就是不知道為什么。

非常感謝您！

編輯版本：

public class ClimbStairs {
    public static void main(String[] args) {
        System.out.println(climbStairs(3));
    }
    public static int climbStairs(int n) {
        int cnt=0,k=0;
        return climb(cnt, k, n);
    }
    public static int climb(int cnt, int k, int n){
        if(k==n){
            cnt  ;
        }
        for(int i=1;i<3;  i){
            if(k<n){
                k =i;
                climb(cnt,k,n);
                k-=i;
            }
        }
        return cnt;
    }
}

uj5u.com熱心網友回復：

每個遞回實作都由兩部分組成：

基本情況- 一種情況（或幾種情況），表示結果已知的邊緣情況。對于這個問題，如果我們選擇跟蹤步數（我會說這不是強制性的），那么基本情況是當樓梯數等于步數時，即k == n。如果我們不跟蹤步數，那么基本情況將用兩個邊緣情況表示：根本沒有樓梯- 不需要臺階，只有一種方法可以走零步，所以輸出是1, 和第二個是當我們只有一個樓梯然后我們必須邁出一步，輸出也是1。
遞回案例- 是遞回呼叫和主要邏輯所在的部分。

在遞回情況下，我們有兩個可能的分支 each k < n：我們可以采取1 步或2 步。因此，我們必須進行兩次代表這些情況的遞回呼叫。所有這些呼叫都可以用圖形表示為一棵樹。為了更好地理解邏輯，您可以從內部創建的第一個方法呼叫樹開始繪制方法呼叫樹，climbStairs()并跟蹤k每個呼叫的值。直到條件k < n是肉，每個頂點都會產生兩個分支。何時k大于或等于n呼叫擊中基本情況. 從底部到頂部，您可以弄清楚每個呼叫的回傳值是什么。

另外，請注意，不是void您的方法必須回傳找到的路徑數。而代表這個數字的第三個引數是多余的。

public static void main(String[] args) {
    System.out.println(climbStairs(1));
    System.out.println(climbStairs(3));
}

public static int climbStairs(int n) {
    if (n < 0) { // cut off the incorrect input
        return 0;
    }
    return climb(n, 0);
}

public static int climb(int n, int k){
    if (k > n) { // an invalid situation
        return 0;
    }
    if (k == n) { // a path was found
        return 1;
    }
    // there are two alternative branches for every k < n
    int count = 0;
    count  = climb(n, k   1); // move one step forward
    count  = climb(n, k   2); // move two steps forward
    return count;
}

正如我上面所說，不需要跟蹤步數。相反，我們可以在進行遞回呼叫的同時減少樓梯的數量。這將允許我們將所有邏輯放在一個方法中。像那樣：

public static int climbStairs(int n) {
    if (n < 0) { // cut off the incorrect input
        return 0;
    }
    if (n == 0) { // a base case when we have NO stairs - we have to take zero steps (there's only ONE way to do that)
        return 1;
    }
    if (n == 1) { // a base case when we have only one stair - we have to take one step (there's only ONE way to do that)
        return 1;
    }
    // there are two alternative branches for every n > 1
    int count = 0;
    count  = climbStairs(n - 1); // move one step forward
    count  = climbStairs(n - 2); // move two steps forward
    return count;
}

輸出

1
3

uj5u.com熱心網友回復：

Java 是按值傳遞的。這意味著您的方法中的cnt變數climbStairs未共享；它對你來說是獨一無二的。當你呼叫時climb，你傳遞它持有的值（0這里每次），并且climb有它自己的變數（也稱為cnt）。它會修改自己的cnt值，該值在該方法結束時被丟棄（當方法結束時，所有引數和所有區域變數總是被丟棄在垃圾中）。

你想退貨 cnt：

// In climbStairs:
return climb(cnt, k, n);

// In climb, at the end:
return cnt;

uj5u.com熱心網友回復：

我們被告知有N步驟。讓n等于采取的兩步數（0 <= n <= N/2）。如果n采取N-2*n兩步，則采取一步。

f(n)當有兩步時，讓等于一步和兩步的組合數n。這只是具有兩個不同專案的多項分布中的一個系數：

m = N-2*n
f(n) = (n m)!/(n!*m!)

為了獲得所需的組合總數，我們只需f(n)對求和n = 0..N/2。

對于N = 3（問題中給出的示例），組合的數量計算如下。

n = 0
m = N-2*n = 3
f(n) = (n m)!/(n!*m!) = 3!/(0!*3!) = 1    # 111

n = 1
m = N-2*n = 1
f(n) = (n m)!/(n!*m!) = 2!/(1!*1!) = 2    # 12 and 21

f(0)   f(1) = 3

對于N = 5，組合數計算如下。

n = 0
m = N-2*n = 5
f(n) = (n m)!/(n!*m!) = 5!/(0!*5!) = 1    # 11111

n = 1
m = N-2*n = 3
f(n) = (n m)!/(n!*m!) = 4!/(1!*3!) = 4    # 2111 1211 1121 1112

n = 2
m = N-2*n = 1
f(n) = (n m)!/(n!*m!) = 3!/(2!*1!) = 3    # 212 221 122

f(0)   f(1)   f(2) = 8

轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/435103.html

標籤：爪哇算法递归回溯传值

上一篇：遞回二叉搜索樹實作-Python

下一篇：在Excel中以公式方式填充沒有水平（行）或垂直（列）重復的陣列（表）