c++ - 爬楼梯 DP 问题基本案例概念

Question

问题: 你正在爬楼梯。需要n步才能到达顶部。 每次您可以跳 1 步、2 步或 3 步。您总共可以通过多少种方式跳到顶部？

我的解释: 好吧，我正在考虑应用递归，因为我可以通过解决类似的子问题来找到解决方案，并且在这个过程中，会有很多重叠的子问题，所以我将数组数据结构来保存类似子问题的名称，这样我就不需要解决同一子问题两次。所以我使用自上而下的 DP 方法。

我的疑问:

现在要构建解决方案，我需要一个基本情况，其中程序流程结束并返回到其父节点(如果将其可视化为树)。所以我所想的基本情况就像我在地板上、在地面 0 时一样，所以我没有其他方法可以达到地面 0 状态，所以这是基本情况。

当n=0时，我应该返回0或1，这是我的疑问？好吧，我已经编写了代码，因此当我返回 1 而不是 n=0 时的 0 时，代码就会工作。那么为什么当n=0时我应该返回1，背后的原因是什么？请帮忙!!!

我的代码:

#include <iostream>
using namespace std;

int climbing_ladders_topDown(int n, int k, int dp[]){
    //Base Case
    if(n==0){
        return 1;
    }

    //LookUp
    if(dp[n]!=0){
        return dp[n];
    }

    //Recursive Case
    int total_num_of_ways = 0;
    for(int jumps=1;jumps<=k;jumps++){
        if(n-jumps>=0){
            total_num_of_ways += climbing_ladders_topDown(n-jumps,k,dp);
        }
    }
    
    dp[n] = total_num_of_ways;
    return dp[n];
}

int main() {
    int num_of_stairs = 4;
    int num_of_jumbs = 3;
    int dp_arr[100] = {0};

    cout<<climbing_ladders_topDown(num_of_stairs,num_of_jumbs,dp_arr);
    
    return 0;
}

输出:7

正确的代码流程(感谢@appleapple):

#include <iostream>
using namespace std;

int climbing_ladders_topDown(int n, int k, int dp[]){

    //Base Case
    if(n==0){
        return 0;
    }

    //LookUp
    if(dp[n]!=0){
        return dp[n];
    }

    //Recursive Case
    int total_num_of_ways = 0;

    for(int jumps=1;jumps<=k;jumps++){
        
        if(n-jumps > 0){
            total_num_of_ways += climbing_ladders_topDown(n-jumps,k,dp);
        }
        
        if(n-jumps == 0){ // have reach the end or ground 0, base so no more move possible in downward direction
            total_num_of_ways += 1; 
        }
        
        if(n-jumps < 0){ //we can't move to -ve state/underground, because it doesn't exist
            total_num_of_ways += 0;
        }

    }
    
    dp[n] = total_num_of_ways;
    
    return dp[n];
}

int main() {

    int num_of_stairs = 4;
    int num_of_jumbs = 3;
    
    int dp_arr[100] = {0};

    cout<<climbing_ladders_topDown(num_of_stairs,num_of_jumbs,dp_arr);
    
    return 0;
}

Answer 1

因为您在这里要求它为1 (f(0) = 1)

for(int jumps=1;jumps<=k;jumps++){
   if(n-jumps>=0){
      total_num_of_ways += climbing_ladders_topDown(n-jumps,k,dp); // here
   }
}

---

如果你想要f(0)=0，因为递归到f(0)不再有意义了(没有可能的解决方案，就像f(-1))

这种情况的算法将变为

if(n<=0){ // not really necessary as implied inside the loop
   return 0; // not possible
}
///...
int total_num_of_ways = 0;
for(int jumps=1;jumps<=k;jumps++){
   if(n-jumps>0){
      total_num_of_ways += climbing_ladders_topDown(n-jumps,k,dp);
   }
   if(n-jumps==0){ // have reach the end, no more move possible
      ++total_num_of_ways; // you put this under n=0
   }
   // if(n-jumps<0){/*do nothing*/}
}

---

注意:f(0) = 0 或 f(0) = 1 提供了一些不同的含义。 (所以算法也改变了)

• f(0) = 1 表示不移动是一种可能的解决方案。
• f(0) = 0 表示至少需要移动 1 步。
• 两者都意味着一旦离开0(无负向移动)就不可能返回，顺便说一句。