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

Question

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

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

我的疑问：

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

当n=0时，我应该return0或1，这是我的疑问？好吧，我已经编写了代码，所以代码在我 return 1 时工作，而不是在 n=0 时工作。那么为什么我应该return 1 when n=0，这背后的原因是什么？请帮忙！！！

我的代码：

#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

在这种计算方法数的问题中，dp[0][..]通常等于1，因为有1种方法可以跳0步，什么都不做。

对于你的问题，因为你已经发现这是一个 DP 问题，它可以通过 for 循环轻松解决，类似于 Tribonacci 序列 (https://oeis.org/A000073) 不同基本案例起点：

#include <iostream>
using namespace std;

const int maxn = 1e3;

int main()
{
    int n; cin >> n;
    int dp[maxn+1];

    //base case
    dp[0] = 1; dp[1] = 1; dp[2] = 2;

    //dp
    for (int i = 3; i <= n; i++)
    {
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
    }

    cout << dp[n];
}

测试：

Input : 3
Output : 4

解释：有 4 种方式：1 + 1 + 1、1 + 2、2 + 1、3。

你的递归和记忆 DP 状态的方式并没有错，只是更笨拙了。

明确地说，将 dp[0] = 1 设置为基本情况只是一件简单且（有点）常规的事情。您完全可以将基本情况作为 dp[1] = 1, dp[2] = 2, dp[3] = 4 并从 dp[4].

开始

代码的复杂度为 O(n)，但如果您需要更大的 n 值，请查看此 post：https://www.hackerearth.com/practice/notes/solving-linear-recurrence-relation/

Answer 2

因为你在这里要求 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（没有负向移动）就不可能返回，顺便说一句。

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

Climbing Stairs DP Problem base case concept

c++

dynamic-programming