Dynamic programming 面接の質問

Dynamic programming 面接で問われる内容

Dynamic programming 面接の質問例

• DPにおけるメモ化と表計算の違いを説明してください。
  良い回答が押さえる点

  • メモ化はトップダウン手法で、再帰呼び出しの結果をキャッシュする。
  • 表計算はボトムアップ手法で、小さな部分問題から順に表を埋める。
  • メモ化は必要な部分問題のみ計算するが、再帰のオーバーヘッドがある。
  • 表計算はすべての部分問題を計算するが、ループで効率的に実装できる。
  • メモ化は自然な再帰構造に適し、表計算は反復処理に適する。

  サンプル回答を見る

  メモ化と表計算はともに動的計画法の実装手法です。メモ化はトップダウンアプローチで、再帰関数の結果を辞書や配列に保存して再利用します。必要な部分問題だけを計算するため無駄が少ないですが、再帰呼び出しによるオーバーヘッドとスタックオーバーフローのリスクがあります。一方、表計算はボトムアップアプローチで、小さな部分問題から順に反復的に表を埋めていきます。すべての部分問題を計算するため、計算量はメモ化と同じでも定数係数が小さいことが多いです。選択は問題の性質と制約によります。例えば、状態空間が広いが解に到達する経路が限られている場合はメモ化が有利で、状態遷移が単純で全状態を網羅する必要がある場合は表計算が適しています。また、メモ化では再帰の深さに注意が必要です。どちらの手法でも、部分問題の重複と最適部分構造の性質を満たす必要があります。

• フィボナッチ数列をDPで実装してください（トップダウンとボトムアップの両方）。
  良い回答が押さえる点

  • トップダウンではメモ化再帰を用いる。
  • ボトムアップではループで配列を埋める。
  • 時間計算量はともにO(n)、空間計算量はトップダウンがO(n)（再帰スタック含む）、ボトムアップがO(1)に改善可能。

  サンプル回答を見る

  フィボナッチ数列のDP実装にはトップダウンとボトムアップの2つの方法があります。トップダウンでは、再帰関数を定義し、計算済みの結果を配列にキャッシュします。ボトムアップでは、基底ケースから順にループで配列を埋めていきます。両者とも時間計算量はO(n)ですが、トップダウンは再帰呼び出しのオーバーヘッドとスタック領域を消費します。ボトムアップは空間計算量をO(1)に最適化可能です（変数2つで計算）。以下にPythonによる完全な実装を示します。

  def fib_top_down(n: int) -> int:
      memo = {0: 0, 1: 1}
      def helper(k: int) -> int:
          if k in memo:
              return memo[k]
          memo[k] = helper(k-1) + helper(k-2)
          return memo[k]
      return helper(n)
  
  # 時間計算量: O(n), 空間計算量: O(n)
  
  def fib_bottom_up(n: int) -> int:
      if n <= 1:
          return n
      a, b = 0, 1
      for _ in range(2, n+1):
          a, b = b, a + b
      return b
  
  # 時間計算量: O(n), 空間計算量: O(1)

• アイテムの重みと価値が与えられたとき、最大価値を得るための0/1ナップサック問題を解いてください。
  良い回答が押さえる点

  • DPテーブルを2次元配列で構築する。
  • 各アイテムについて、容量を増やしながら最大価値を更新する。
  • 状態遷移はアイテムを選ぶか選ばないかの2択。

  サンプル回答を見る

  0/1ナップサック問題では、各アイテムを1回だけ使える制約の下で、容量制限内で価値の合計を最大化します。DPテーブルdp[i][w]を「最初のi個のアイテムから重さ制限wで得られる最大価値」と定義します。遷移は、i番目のアイテムを選ばない場合はdp[i-1][w]、選ぶ場合はdp[i-1][w - weight[i]] + value[i]の大きい方を採用します。初期条件はdp[0][*]=0。最終的にdp[n][capacity]が答えです。時間計算量はO(n * capacity)、空間計算量はO(n * capacity)ですが、1次元配列に圧縮可能です。

  def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
      n = len(weights)
      # 1次元配列で空間最適化
      dp = [0] * (capacity + 1)
      for i in range(n):
          # 容量を降順に更新することで、各アイテムを1回だけ使う
          for w in range(capacity, weights[i] - 1, -1):
              dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
      return dp[capacity]
  
  # 時間計算量: O(n * capacity), 空間計算量: O(capacity)

• 配列内の最長増加部分列の長さを見つけてください。
  良い回答が押さえる点

  • DP配列dp[i]を位置iで終わる最長増加部分列の長さと定義する。
  • 各位置iについて、それ以前のj < iでnums[j] < nums[i]ならdp[i] = max(dp[i], dp[j]+1)。
  • 最終的な答えはmax(dp)。
  • O(n^2)時間、O(n)空間。

  サンプル回答を見る

  最長増加部分列（LIS）問題では、与えられた配列から順序を保ったまま増加する部分列の最大長を求めます。DPでは、dp[i]をindex iで終わるLISの長さと定義します。初期値は1（自分自身のみ）。各iについて、全てのj < iを調べ、nums[j] < nums[i]ならdp[i] = max(dp[i], dp[j]+1)と更新します。最終的にdp配列の最大値が解です。この方法はO(n^2)ですが、二分探索を用いたO(n log n)解法も存在します。以下にO(n^2)の実装を示します。

  def length_of_LIS(nums: list[int]) -> int:
      n = len(nums)
      if n == 0:
          return 0
      dp = [1] * n
      for i in range(n):
          for j in range(i):
              if nums[j] < nums[i]:
                  dp[i] = max(dp[i], dp[j] + 1)
      return max(dp)
  
  # 時間計算量: O(n^2), 空間計算量: O(n)

• 2つの文字列間の編集距離（レーベンシュタイン距離）を計算してください。
  良い回答が押さえる点

  • 2次元DPテーブルdp[i][j]を「文字列Aのi文字目までとBのj文字目までの編集距離」と定義。
  • 遷移は挿入、削除、置換の3操作に対応。
  • 初期条件は片方の文字列が空の場合。

  サンプル回答を見る

  編集距離（レーベンシュタイン距離）は、文字列AをBに変換するのに必要な最小の操作回数です。操作は挿入、削除、置換の3種類。dp[i][j]をA[0:i]とB[0:j]の編集距離とします。初期化はdp[i][0]=i（削除）、dp[0][j]=j（挿入）。遷移は、A[i-1]==B[j-1]ならdp[i][j]=dp[i-1][j-1]、それ以外ならdp[i][j]=1+min(dp[i-1][j]（削除）, dp[i][j-1]（挿入）, dp[i-1][j-1]（置換）)です。最終的にdp[m][n]が解。時間・空間ともO(mn)ですが、空間は2行のみでO(min(m,n))に改善可能。

  def edit_distance(A: str, B: str) -> int:
      m, n = len(A), len(B)
      # 2行のみの空間最適化
      prev = list(range(n + 1))
      for i in range(1, m + 1):
          curr = [i] + [0] * n
          for j in range(1, n + 1):
              if A[i-1] == B[j-1]:
                  curr[j] = prev[j-1]
              else:
                  curr[j] = 1 + min(prev[j], curr[j-1], prev[j-1])
          prev = curr
      return prev[n]
  
  # 時間計算量: O(mn), 空間計算量: O(n)

• 指定された金額を作るのに必要な最小のコインの数を見つけるコイン交換問題を解いてください。
  良い回答が押さえる点

  • コインの種類と目標金額が与えられたとき、最小コイン数を求める。
  • DP配列dp[i]を金額iを作る最小コイン数と定義。
  • dp[0]=0、各コインcについてdp[i]=min(dp[i], dp[i-c]+1)。

  サンプル回答を見る

  コイン交換問題（最小コイン数）は、無限に使えるコインで目標金額をちょうど作る最小枚数を求めます。DPでは、dp[i]を金額iを作る最小コイン数と定義し、dp[0]=0、他は大きな値で初期化します。各コインcに対して、金額cから目標まで順にdp[i] = min(dp[i], dp[i-c] + 1)と更新します。この方法はコインの組み合わせを考慮し、無制限に使えるため内側のループは昇順で回します。時間計算量はO(目標金額 * コイン種類数)、空間はO(目標金額)です。

  def coin_change(coins: list[int], amount: int) -> int:
      INF = float('inf')
      dp = [INF] * (amount + 1)
      dp[0] = 0
      for coin in coins:
          for i in range(coin, amount + 1):
              dp[i] = min(dp[i], dp[i - coin] + 1)
      return dp[amount] if dp[amount] != INF else -1
  
  # 時間計算量: O(amount * len(coins)), 空間計算量: O(amount)

• 一度に1歩または2歩で階段を上る方法の数を数えてください。
  良い回答が押さえる点

  • 階段のn段目に達する方法の数は、n-1段目とn-2段目から来る方法の和。
  • これはフィボナッチ数列と同じ漸化式（ただしf(1)=1, f(2)=2）。
  • DPを使うか、単純なループでO(n)時間、O(1)空間で解ける。

  サンプル回答を見る

  階段を1歩または2歩で上る方法の数は、フィボナッチ数列の変形です。n段目に達する方法の数をf(n)とすると、f(1)=1（1歩）、f(2)=2（1+1または2）、f(n)=f(n-1)+f(n-2)（n>=3）。これはDPの典型的な例で、ボトムアップに計算できます。空間最適化も可能で、2変数でループを回せばO(1)空間で済みます。ただし、nが大きい場合はオーバーフローに注意が必要です。以下にPython実装を示します。

  def climb_stairs(n: int) -> int:
      if n <= 2:
          return n
      a, b = 1, 2
      for _ in range(3, n + 1):
          a, b = b, a + b
      return b
  
  # 時間計算量: O(n), 空間計算量: O(1)

• DP問題を解くための段階的なアプローチを、部分問題の特定からコーディングまで説明してください。
  良い回答が押さえる点

  • 部分問題の特定: 問題をより小さな部分問題に分割できるか確認。
  • 状態定義: 部分問題の解を表す状態変数を定義。
  • 遷移式: 状態間の関係を数式で表す。
  • 初期条件: 基底ケースを設定。
  • 実装: トップダウン（メモ化）またはボトムアップ（表計算）を選択。

  サンプル回答を見る

  DP問題を解くための段階的アプローチは以下の通りです。まず、問題が最適部分構造と部分問題の重複を持つことを確認します。次に、部分問題の解を表す状態を定義します。例えば、配列のインデックスやパラメータなどです。そして、状態間の遷移式（漸化式）を導きます。これは「今の状態」と「より小さな状態」の関係です。その後、基底ケース（最小の部分問題の解）を設定します。最後に、実装方法を選択します。トップダウンは再帰とメモ化で自然に書けますが、ボトムアップは反復で効率的です。実装後は、計算量（時間・空間）を評価し、必要に応じて空間最適化を行います。コーディングでは、配列の範囲外アクセスに注意し、テストケースで確認します。このプロセスにより、複雑に見える問題も構造的に解くことができます。

準備方法

• ナップサック、LCS、グリッド問題などの一般的なDPパターンをマスターしましょう。
• コーディングの前に漸化式をゼロから書く練習をしましょう。
• まず力技の再帰から始め、メモ化を追加し、必要に応じて表計算に変換しましょう。
• 空間最適化テクニック（例：2D DPを1Dに削減）を使用して効率を向上させましょう。
• 各パターンから少なくとも3〜4問解いて、DPを認識する直感を養いましょう。

よくある質問