java - 一次进行 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?
• Generate All Possible Combinations - Java
• 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

可以使用动态规划轻松解决。

如果您已经解决了第N步，那么要达到N+1步将是以下任一 -

• 实现第 N 步 + 单 步到第 N+1 步的可能方法
• 实现第 N-1 步 + 双 步到第 N+1 步的可能方法
• 实现第 N-2 步 + 三重步到第 N+1 步的可能方法

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