时间戳

首页 > 解决方案 > 1、2、3步的第n步组合数‽

java - 1、2、3步的第n步组合数‽

问题描述

我正在做以下编程练习：第 n 步的组合数。声明是：

您需要到达第 n 级楼梯，挑战是通过一次走 1,2 或 3 步来获得到达第 n 级楼梯的不同方式的数量。

因此，例如有多少种方法可以到达第三步。你可以到达那里 4 如下所示：[1,1,1] [1,2] [2,1] [3]

编写方法 findCombs 找到所有不同的方法组合，你可以到达第 n 步！

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

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；如果 step 是 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));
    }
}

我们如何计算一般情况？

我读过了：

那么，我们如何计算到第 n 步的组合数，一次走 1、2 或 3 步呢‽</p>

编辑：在@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、1 为 4、2 为 5 时，它输出 -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;‽</p>

标签： javafunctionmathintcombinations

解决方案

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

如果你已经解决到第 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)

推荐阅读