algorithm - ？当允许负整数和/或零步时，结果是否可以在(爬楼梯/ Frog 跳)中找到？

Question

序言:

当问楼梯问题时，通常给定的允许步幅数组是 [1,2,3]

在 SO 上看到很多相同问题的例子，比如 n-steps-with-1-2-or-3-steps-taken-how-many-ways-to-get-to-the-top

我的问题与此有关，但要为允许的步速包括负数和零的情况寻找证据。

有些事情是显而易见的，比如

• 如果所有步长都是正数，那么可能的方法数是有限且可解的。
• 如果任何步长为零，那么数字可能的方式变得无限。
• 如果至少有一个负步长允许并且步长的任何组合总和为零然后可能的方式变得无限多。

示例:

countSteps(stairSize:=5, [  1,2,3]) // 17
countSteps(stairSize:=5, [0,1,2,3]) // 17...

countSteps(stairSize:=5, [-2,-1  ]) // zero ways
countSteps(stairSize:=5, [-2,-1,0]) // infinitely zero ways

countSteps(stairSize:=5, [2,4]) // zero ways

countSteps(stairSize:=5, [   3]) // zero ways
countSteps(stairSize:=5, [-1,3]) // infinite ways

countSteps(stairSize:=5, [6,7,8]) // zero ways

问题:

? Can you determine whether given
    a stair size (1.. for now)
    and an array of allowable steps
    is the result find-able ?

Answer 1

您可以分两部分进行此操作:

• 首先，创建一个大小为 stairSize 的 bool 数组，表示给定的台阶是否可以从底部台阶到达。将所有值初始化为“false”(包括底部步骤)，然后使用搜索算法(例如 BFS 或 DFS)找到所有可到达的步骤并将它们设置为“true”。
  • 如果最上面的步骤永远不会变为“真”，那么就没有办法从底部到达最上面的步骤；返回 0。
  • 否则，如果最后一步的结果为“真”，则存在循环；返回∞。 (由于问题中的对称性，如果存在循环，底部步骤将始终以“真”结束。)
• 接下来，创建一个大小为 stairSize 的整数数组，表示到达给定步骤的方法数。将底部步骤初始化为 1，将所有其他值初始化为 0，然后使用递归来填充此数组。 (例如，像这样的东西:

  private int getNumWaysToReachStep(
          final int targetStep,
          final boolean[] isStepReachable,
          final int[] numWaysToReachStep,
          final int[] numStepsAtATimeArr) {
      if (targetStep == 0) {
          return 1;
      } else if (targetStep < 0 || targetStep >= isStepReachable.length) {
          return 0;
      } else if (numWaysToReachStep[targetStep] != 0 || ! isStepReachable[targetStep]) {
          return numWaysToReachStep[targetStep];
      }
      int result = 0;
      for (final int numSteps : numStepsAtATimeArr) {
          result += getNumWaysToReachStep(targetStep - numSteps, isStepReachable,
                        numWaysToReachStep, numStepsAtATimeArr);
      }
      numWaysToReachStep[targetStep] = result;
      return result;
  }
  

  )

总体而言，这需要 O(stairSize · |numStepsAtATimeArr|) 时间和 O( stairSize) 额外的空间。