一次1、2或3步到第n步的组合数‽

Question

我正在进行以下编程练习：Number of combinations to the nth step。语句为：

You need to get to the nth stair, the challenge is to get the number of different ways you can get to the nth stair with taking 1,2 or 3 steps at a time.

So for exmaple how many ways to get to the 3rd step. You can get there 4 was as shown here: [1,1,1] [1,2] [2,1] [3]

Write the method findCombs that finds all the different combinations of ways you can reach the nth step!

到目前为止，我已经手工计算了这些组合：

1 -> [1]

2 -> [1,1], [2]

3 -> [1,1,1], [1,2], [2,1], [3]

4 -> [1,1,1,1],[2,1,1][1,2,1],[1,1,2],[2,2],[3,1],[1,3]

5 -> [1,1,1,1,1],[2,1,1,1],[1,2,1,1],[1,1,2,1],[1,1,1,2],[2,2,1],[2,1,2],[1,2,2],[3,2],[2,3]

6 -> [1,1,1,1,1,1],[2,1,1,1,1],[1,2,1,1,1],[1,1,2,1,1],[1,1,1,2,1],[1,1,1,1,2],[2,2,1,1],[2,1,2,1],[2,1,1,2],[1,2,2,1],[1,1,2,2],[2,2,2],[3,2,1],[2,3,1],[1,2,3],[3,3]

如果正确，我们对每个步数有以下组合：

1: 1; 2: 2; 3: 4; 4: 7; 5: 10; 6: 16...

到目前为止我已经写了，如果步数为0或负数，它应该输出-1；如果步数是1或2，我们分别算1或2。

public class Stairs {
    public int findCombs(int n){
      if(n <= 0) return -1;
      if(n <= 2) return n;
      return 0;
    }
}

正在接受测试：

import org.junit.Assert;
import org.junit.Test;

public class mainTests {

    @Test
    public void test_n_3(){
        Stairs stairs = new Stairs();
        Assert.assertEquals(4,stairs.findCombs(3));
    }

    @Test
    public void test_n_7(){
        Stairs stairs = new Stairs();
        Assert.assertEquals(44,stairs.findCombs(7));
    }

    @Test
    public void test_n_25(){
        Stairs stairs = new Stairs();
        Assert.assertEquals(2555757,stairs.findCombs(25));
    }

    @Test
    public void test_n_0(){
        Stairs stairs = new Stairs();
        Assert.assertEquals(-1,stairs.findCombs(0));
    }
}

我们如何计算一般情况？

我已阅读：

How to generate the power-set of a given List?
https://www.superprof.es/apuntes/escolar/matematicas/probabilidades/combinatoria/combinaciones.html
Java program to calculate the combinations function

那么，一次1步2步3步到第n步的组合数怎么计算‽

编辑：根据@Saurav Kumar Singh 的回答，我写了以下内容：

public class Stairs {
    public int findCombs/**/(int n){
      if(n <= 0) return -1;
      if(n <= 2) return n;
      if(n == 3) return 4;
      return findCombs(n-1) + findCombs(n-2) + findCombs(n-3);
    }
}

并且它通过了测试。但是我想删除硬编码的基本情况：

if(n == 3) return 4;

我试过：

public class Stairs {
    public int findCombs(int n){
      if(n <= 0) return -1;
      if(n <= 2) return n;
      return findCombs(n-1) + findCombs(n-2) + n-3 > 0 ? findCombs(n-3) : 1;
    }
}

然而，当我们想要 3 人的楼梯、4 人的 1 人、5 人的 2 人的楼梯时，它会输出 -1...

我也试过：

public class Stairs {
    public int findCombs(int n){
      if(n <= 0) return 1;
      if(n <= 2) return n;
      return findCombs(n-1) + findCombs(n-2) + findCombs(n-3);
    }
}

然而当n为负数或0时，它输出1，而不是-1

如何编写解决方案而不需要包含：if(n == 3) return 4;‽

Answer 1

可以使用动态编程轻松解决。

如果你已经解决了 Nth step 那么要达到 N+1th step 将是这个 -

达到第 Nth 步的可能方法 + single step 到 N+1th
达到第 N-1 步的可能方法 + double 步到第 N+1 步
达到第 N-2 步的可能方法 + tripple 步到第 N+1 步

因此S(N+1) = S(N) + S(N-1) + S(N-2)

一次1、2或3步到第n步的组合数‽

Number of combinations to the nth step taking 1, 2 or 3 steps at a time‽

java

math

int

combinations

function