Decode Waysと経路のカウント
decode-ways（数字から文字へのマッピング）をFibonacciに似たDPとして解き、次に可変ステップ幅の階段を上る経路数を数えます。
「Decode Waysと経路のカウント」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
Decode Ways 問題
Decode Ways（LeetCode 91）では、数字の文字列を文字に対応付けます。'A'=1、'B'=2、...、'Z'=26 です。エンコードされた数字の文字列が与えられたとき、それをデコードする異なる方法の数を数えます。たとえば、'12' は 'AB'（1+2）または 'L'（12）としてデコードできるため、方法は 2 通りです。'226' は 'BZ'（2+26）、'VF'（22+6）、または 'BBF'（2+2+6）としてデコードできるため、3 通りです。先頭のゼロによって無効になるデコードもあります。
# Encoding: A=1, B=2, ..., Z=26
# '12' → 'AB' or 'L' → 2 ways
# '226' → 'BZ' or 'VF' or 'BBF' → 3 ways
# '06' → invalid (no letter for '0')
# '10' → 'J' only → 1 way (only valid as 10, not 1+0)
s = '226'
print('Decodings for', s, ':', 3) # Expected: 3Decode Ways のDP定式化
dp[i] を s[:i] のデコード方法の数とします。基本ケースは、dp[0] = 1（空文字列は1通り）で、s[1] != '0' なら dp[1] = 1、それ以外なら0です。遷移では、s[i-1] != '0' なら dp[i-1] を加えます（1桁のデコード）。また、10 ≤ int(s[i-2:i]) ≤ 26 なら dp[i-2] を加えます（2桁のデコード）。これは本質的には、妥当性チェックを加えたフィボナッチパターンです。
def num_decodings(s):
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1 # empty prefix
dp[1] = 0 if s[0] == '0' else 1
for i in range(2, n + 1):
# Single digit decode
if s[i-1] != '0':
dp[i] += dp[i-1]
# Two digit decode
two_digit = int(s[i-2:i])
if 10 <= two_digit <= 26:
dp[i] += dp[i-2]
return dp[n]
print(num_decodings('12')) # 2
print(num_decodings('226')) # 3
print(num_decodings('06')) # 0先頭のゼロに関する注意点
Decode Ways で最も難しいのは、ゼロの扱いです。単独の「0」はデコードできません（0に対応する文字はないため）。そのため、s[i-1] == '0' の場合は dp[i-1] を加えません。2桁目の「0」が有効なのは、2桁の数が10または20の場合だけです。30や40（およびそれ以上）は26を超えるため無効です。two_digit ≤ 26 だけでなく、必ず 10 ≤ two_digit ≤ 26 を確認してください。
def num_decodings(s):
if not s or s[0] == '0': return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 # s[0] != '0' guaranteed by guard above
for i in range(2, n + 1):
one = int(s[i-1])
two = int(s[i-2:i])
if one != 0: dp[i] += dp[i-1] # valid single digit
if 10 <= two <= 26: dp[i] += dp[i-2] # valid two digits
return dp[n]
print(num_decodings('10')) # 1 (only 'J')
print(num_decodings('30')) # 0 (30 > 26, '0' alone invalid)
print(num_decodings('100')) # 0 (dp[2]=1 then '00' invalid, single '0' invalid)Decode Ways の空間最適化
フィボナッチ数列と同様に、デコード方法の漸化式は2つ前までしか参照しないため、2つの変数を使って空間計算量をO(n)からO(1)に削減できます。2つ前の値を保持する prev2 と、1つ前の値を保持する prev1 を使います。各ステップで両方から curr を計算し、その後に値をずらします。これはフィボナッチ数列における「2変数への最適化」と同じです。
def num_decodings_o1(s):
if not s or s[0] == '0': return 0
prev2 = 1 # dp[0]
prev1 = 1 # dp[1]
for i in range(2, len(s) + 1):
curr = 0
if s[i-1] != '0':
curr += prev1
two = int(s[i-2:i])
if 10 <= two <= 26:
curr += prev2
prev2, prev1 = prev1, curr
return prev1
print(num_decodings_o1('226')) # 3
print(num_decodings_o1('12')) # 2
print(num_decodings_o1('0')) # 0階段を上る経路の数え上げ
Climbing Stairs（LeetCode 70）では、1回に1段または2段上れるとき、n段の階段を上る方法が何通りあるかを求めます。これはまさにフィボナッチ数列です。ways(n) = ways(n-1) + ways(n-2) となります。ways(1)=1、ways(2)=2、ways(3)=3、ways(4)=5 です。1回に最大 k 段まで上れる場合にも一般化でき、ways(n) = sum(ways(n-1), ..., ways(n-k)) となります。
def climb_stairs(n):
if n <= 2: return n
prev2, prev1 = 1, 2
for _ in range(3, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1
for i in range(1, 8):
print(f'climb_stairs({i}) = {climb_stairs(i)}')
# 1, 2, 3, 5, 8, 13, 21 — Fibonacci!段数が可変な階段登り
指定された集合（例：{1, 3, 5}）から任意の段数を選んで上れる場合、漸化式は dp[i] = sum(dp[i-k] for k in steps if i-k >= 0) となります。メモリを効率化するには、サイズ max(steps) のスライディングウィンドウを使います。これは非有界ナップサックにおける個数カウントの変種で、各段数を何度でも使えます。
def count_ways(n, steps):
dp = [0] * (n + 1)
dp[0] = 1 # one way to stay at ground
for i in range(1, n + 1):
for step in steps:
if i >= step:
dp[i] += dp[i - step]
return dp[n]
# Steps of 1 or 2 (classic climbing stairs)
print(count_ways(5, [1, 2])) # 8
# Steps of 1, 3, or 5
print(count_ways(5, [1, 3, 5])) # 5
# Steps of 2 or 3
print(count_ways(6, [2, 3])) # 3 (2+2+2, 3+3, 2+4-invalid, 2+2+2, 3+3, 3+2+1-no...)階段登りの最小コスト
Min Cost Climbing Stairs（LeetCode 746）では、各段にコストが設定されており、頂上まで到達するための最小コストを求めます。段 i からは i+1 または i+2 へ移動できます。漸化式は dp[i] = cost[i] + min(dp[i-1], dp[i-2]) です。段0または段1から開始できます。答えは min(dp[n-1], dp[n-2]) です。
def min_cost_climbing(cost):
n = len(cost)
if n == 1: return cost[0]
dp = [0] * n
dp[0] = cost[0]
dp[1] = cost[1]
for i in range(2, n):
dp[i] = cost[i] + min(dp[i-1], dp[i-2])
return min(dp[-1], dp[-2]) # can start from step 0 or 1
print(min_cost_climbing([10, 15, 20])) # 15
print(min_cost_climbing([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])) # 6Decode Ways II：ワイルドカードの数字
Decode Ways II（LeetCode 639）では、1～9の任意の数字を表せるワイルドカード文字「*」が導入されます。これにより、有効なデコード方法の数が大幅に増加します。単独の「*」は、1～9の任意の数字として9通りを表します。2つの「*」を組み合わせると、2桁の組み合わせは9×9通り考えられますが、そのうち26以下のものだけが有効です（11～19が9通り、21～26が6通りなので、「**」は15通り）。注意深い場合分けが必要です。
def num_decodings_ii(s):
MOD = 10**9 + 7
prev2, prev1 = 1, 9 if s[0] == '*' else (0 if s[0] == '0' else 1)
for i in range(1, len(s)):
curr = 0
c, p = s[i], s[i-1]
# Single digit
if c == '*': curr += 9 * prev1
elif c != '0': curr += prev1
# Two digits
if p == '*' and c == '*': curr += 15 * prev2 # 11-19(9) + 21-26(6)
elif p == '*': curr += (2 if c <= '6' else 1) * prev2
elif c == '*': curr += (9 if p == '1' else (6 if p == '2' else 0)) * prev2
else:
two = int(p + c)
if 10 <= two <= 26: curr += prev2
prev2, prev1 = prev1, curr % MOD
return prev1 % MOD
print(num_decodings_ii('*')) # 9
print(num_decodings_ii('1*')) # 18フィボナッチ数列との関係
Decode Ways と Climbing Stairs は、どちらも実質的にはフィボナッチ系の問題です。dp[i] が dp[i-1] と dp[i-2] だけに依存するDPは、フィボナッチ型であり、空間計算量O(1)で解けます。妥当性チェック（ゼロの数字や段数の種類）によって有効な遷移は変わりますが、2つ前まで参照する基本構造は変わりません。この系統の問題だとすぐに認識できることは、面接で素早く解くために役立つ重要なパターンです。
# Fibonacci family: dp[i] = f(dp[i-1], dp[i-2])
# Fibonacci itself: dp[i] = dp[i-1] + dp[i-2]
# Climbing stairs: dp[i] = dp[i-1] + dp[i-2]
# Decode ways: dp[i] = (dp[i-1] if one_valid) + (dp[i-2] if two_valid)
# Min cost stairs: dp[i] = cost[i] + min(dp[i-1], dp[i-2])
# House robber: dp[i] = max(dp[i-1], nums[i] + dp[i-2])
# All solved with 2 rolling variables:
prev2, prev1 = 0, 1
for _ in range(10):
prev2, prev1 = prev1, prev1 + prev2
print('Fibonacci F(10):', prev1) # 89グリッド上の経路の数え上げ
関連する数え上げ問題として、m×nのグリッドで、右または下にしか移動できない場合に、左上から右下まで進む異なる経路が何通りあるかを考えます。答えは二項係数C(m+n-2, m-1)です。DP解法では2次元テーブルを埋め、dp[i][j] = dp[i-1][j] + dp[i][j-1] とします。これはフィボナッチ型の階段問題を2次元にしたもので、各セルは上のセルと左のセルの合計になります。
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
# Or use math for O(1) solution
import math
def unique_paths_math(m, n):
return math.comb(m + n - 2, m - 1)
print(unique_paths(3, 7)) # 28
print(unique_paths_math(3, 7)) # 28
print(unique_paths(3, 3)) # 6面接での落とし穴のまとめ
Decode Ways でよくある落とし穴は次のとおりです。(1) 「0」単独は無効であることを忘れないこと。dp[i-1] を加える前に、必ず s[i-1] != '0' を確認してください。(2) two_digit <= 26 だけを使い、two_digit >= 10 を確認しないこと。「07」を「G」としてデコードしてはいけません。(3) dp[n] ではなく dp[n-1] を返してしまうこと。テーブルは1始まりで考えるため、dp[n] が文字列全体に対応します。DPテーブルの要素数が入力より1つ多い場合は、配列のインデックスを必ず再確認してください。
# Common bug: checking two_digit <= 26 without >= 10
def buggy_decode(s):
dp = [0] * (len(s) + 1)
dp[0] = dp[1] = 1
for i in range(2, len(s) + 1):
if s[i-1] != '0': dp[i] += dp[i-1]
two = int(s[i-2:i])
# BUG: '07' gives two=7, and 7 <= 26 would add dp[i-2]
# Fix: require two >= 10
if 10 <= two <= 26: dp[i] += dp[i-2] # CORRECT
return dp[len(s)]
print(buggy_decode('06')) # 0 (correct, '0' alone invalid)
print(buggy_decode('07')) # 0 (correct, '07' not valid, '0' alone invalid)
print(buggy_decode('27')) # 1 (only 'BG', 27>26 so no two-digit)理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、Decode Ways は、1桁（ゼロ以外）および2桁（10～26）のデコードに対する妥当性チェックを伴う、フィボナッチ型の漸化式に従うこと、Climbing Stairs と Min Cost Staircase は、O(1)空間で解ける純粋なフィボナッチ系の変種であること、そして2つ前まで参照するフィボナッチ系の問題だと認識できれば、面接中の時間を大幅に節約できることを学びました。次は、グリッド上のUnique PathsとMinimum Path Sumを通して、2次元DPを学びます。
よくある質問
「Decode Waysと経路のカウント」レッスンは無料ですか？
はい。「Decode Waysと経路のカウント」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「Decode Waysと経路のカウント」で何を学びますか？
decode-ways（数字から文字へのマッピング）をFibonacciに似たDPとして解き、次に可変ステップ幅の階段を上る経路数を数えます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「Decode Waysと経路のカウント」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- House Robber：取るかスキップするかの漸化式
- 最大部分配列と最大積部分配列
- Word Breakと文字列の分割
- Decode Waysと経路のカウント