2段上がる、3段上がる、5段上がる…というように素数段だけ上がることにするとき、n段の階段を上がる方法は何通りあるでしょうか？


はじめまして、Python初心者です。

1段、2段上がる、3段上がる、5段上がる…というように一段または素数段だけ上がることにするとき、n段の階段を上がる方法は何通りあるでしょうか？
ただし、nは50以下の自然数。

ルール：組み込み関数のみ使用。list/tuple/set/dictionaryを使用。

期待：フィボナッチ数列使えばいけると思った。例えば、11段の上がり方は、（11－1）段、（11－2）、（11－3）、（11－5）、（11－7）、（11－9）、（11－11）段までの上り方の総数の和。

実際：関数定義が禁止だから使えない  
論理的に考えれば解けるらしいので

プログラミングに落とし込むところが分からないのでフローチャートすら書けない状態。

よろしくお願いいたします。回答していただけるだけで有難いです。




>
> 期待：フィボナッチ数列使えばいけると思った。例えば、11段の上がり方は、（11－1）段、（11－2）、（11－3）、（11－5）、（11－7）、（11－9）、（11－11）段までの上り方の総数の和。
>
> 実際：関数定義が禁止だから使えない

一旦、フィボナッチ数列は脇に置いて、DP(Dynamic Programming: 動的計画法)で解いてみます。

[code]

    ## prime numbers
    max_step, primes = 50, [1, 2]
    for i in range(primes[-1]+1, max_step+1):
      for j in primes[1:][:]:
        if i%j == 0: break
        if i < 2*j: primes.append(i); break
    
    #print(primes)
    
    ## sum all steps with DP
    n = 11
    steps = [i for i in primes if i <= n]
    dp = [1] + [0]*n
    for i in range(1, n+1):
      for p in steps:
        if (i-p >= 0):
          dp[i] += dp[i-p]
    
    sum_steps = dp[n]
    print(sum_steps)
    
    #
    652
    
[/code]

> 回答していただけるだけで有難いです。

上記のコードに関して解説はしません。DP に関して興味が湧いてきたのであれば調べてみて下さい。

