###わからないこと
『プログラマ脳を鍛える 数学パズル』という書籍の「Q15 階段で立ち話」において、動的計画法を用いた解法の解説に
「2人が同じ段になる」ということは「1人が偶数回の移動で逆の位置に着く」、と言い換えられますので
とあるのですが、このロジックがわかりません。
解答をいただければ幸いです。
###前提
Q15の問題文を一部抜粋します。
ある階段を下からAさんが上がっていくと同時に、上からBさんが下りてきます。
階段は1段ずつ上がる(下りる)必要はなく、最大で3段まで飛ばして進む(一気に4段進む)ことができます。ただし、何段飛ばす時も、1回の移動にかかる時間は同じとします。
2人が同時に1回ずつ移動するとき、「2人が同じ段に止まるような動き方」が何通りあるかを考えます。
###試したこと
問題について把握するため、解答にあったコードの写経をしました。
(rubyで書かれていたものをそのままPythonで書き換えていますが…)
dpが「Bさんがi回目の移動でインデックスの位置に着くパターン数」を表すことは把握できましたが、なぜ目的の数が得られるのかはわかりませんでした…
N = 10 # 段数 STEPS = 4 # 歩幅 dp = [0] * (N + 1) # Bさんのいる位置のパターン cnt = 0 dp[N] = 1 # 開始位置を初期化 for i in range(N): # i回目の移動後にBさんがいる位置のパターンを計算 for j in range(N + 1): # 移動元の段 for k in range(1, STEPS + 1): if k > j: break dp[j - k] += dp[j] dp[j] = 0 # 移動元をクリア ''' ここがわからない Aさんの初期位置に偶数回目の移動で到達する数を足し合わせている? ''' cnt += dp[0] if i % 2 == 1 else 0 print(cnt)
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2017/11/15 05:42