1、2 或 3 步爬楼梯的方式数量 - 记忆

Question

我必须计算一个人一次走 1 步、2 步或 3 步爬楼梯的方式有多少种。我知道如何做到这一点，例如 f(n-1) + f(n-2) + f(n-3) 但我想知道为什么在我的实现中（与上述不同）我没有得到正确的答案。我正在使用 for 循环。问题是每次返回一个非零值但该值包含一个预先计算的答案，因此我的代码不使用。我需要做哪些改变？

#include <iostream>
#include <map>

using namespace std;
int nWays = 0;

int stepPerms(int n, map<int, int> &memo) {

    if (memo.find(n) != memo.end())
        return memo[n];
    if (n == 0)
        return 0;
    if (n < 0)
        return -1;
    for (int i = 1; i <= 3; i++) {
        int retVal = stepPerms(n - i, memo);
        if (retVal == 0)
            memo[n] = ++nWays;
    }
    return memo[n];
}

int main() {
    map<int, int> memo;
    cout << stepPerms(5, memo);//cout << stepPerms(3) << endl;
}

Answer 1

我是这样解决的:

#include <iostream>
#include <map>

using namespace std;
map<int, int> memo;

int stepPerms(int n) {
    if (memo.find(n) != memo.end())
        return memo[n];
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    if (n == 3)
        return 4;
    for (int i = 1; i <= 3; i++)
        memo[n] += stepPerms(n - i);
    return memo[n];
}

int main() {
    cout << stepPerms(27);
}

1、2 或 3 步爬楼梯的方式数量 - 记忆

Number of ways in which you can climb a staircase with 1, 2 or 3 steps - memoization

c++

dynamic-programming

memoization