Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonで階段を上る方法をいくつ見つけるかをプログラムする

n段の階段があり、一度に1段または2段の階段を上ることができるとします。階段を上るユニークな方法の数を返す関数を定義する必要があります。

ステップの順序は変更しないでください。そのため、ステップの異なる順序はそれぞれ1つの方法としてカウントされます。答えが非常に大きい場合は、結果を10 ^ 9+7で変更します

したがって、入力がn =5のような場合、8つの固有の方法があるため、出力は8になります-

  • 1、1、1、1、1
  • 2、1、1、1
  • 1、2、1、1
  • 1、1、2、1
  • 1、1、1、2
  • 1、2、2
  • 2、1、2
  • 2、2、1

これを解決するには、次の手順に従います-

  • dp：=サイズn + 1の配列で、0で埋めます
  • dp [1]：=1
  • 2からn+1の範囲のiについては、
    • dp [i]：=dp [i-1] + dp [i-2]
  • dpmodmの最後の要素を返す

理解を深めるために、次の実装を見てみましょう-

例

m =(10**9)+7
class Solution:
   def solve(self, n):
      dp=[0 for _ in range(n+2)]
      dp[1]=1
      for i in range(2,n+2):
         dp[i]=dp[i-1]+dp[i-2]
      return dp[-1] % m
ob = Solution()
print(ob.solve(5))

入力

5

出力

8

  1. Pythonで捕まえることができる雨の総量を見つけるためのプログラム

    n個の非負の整数の配列があるとします。これらは、各バーの幅が1である高さを表しており、雨が降った後にどれだけの水を捕まえることができるかを計算する必要があります。したがって、マップは次のようになります- ここでは、8つの青いボックスがあることがわかります。したがって、出力は8になります。 これを解決するには、次の手順に従います- スタックst、water：=0およびi：=0を定義します whilei<身長のサイズ =height [i]の場合、iをスタックにプッシュし、iを1増やします それ以外の場合 x：=スタックトップ要素、スタックからトップを削除 スタックが空でない場合

  2. Pythonでツリーを2つのツリーに分割できる方法の数を数えるプログラム

    値0、1、および2を含む二分木があるとします。ルートには少なくとも1つの0ノードと1つの1ノードがあります。ここで、ツリーのエッジを削除し、ツリーが2つの異なるツリーになる操作があるとします。 2つのツリーのいずれにも0ノードと1ノードの両方が含まれないように、1つのエッジを削除できる方法の数を見つける必要があります。 したがって、入力が次のような場合 0から2のエッジしか削除できないため、出力は1になります。 これを解決するには、次の手順に従います- count：=[0、0、0] 関数dfs（）を定義します。これはノードを取ります ノードがnullでない場合、 pre：=