DPL_2_A – 巡回セールスマン問題

問題のリンク

この問題のポイント

• dfs(depth first search)でメモ化再帰
• 頂点数が少ないので、bitで状態を管理可能（詳しくは以下、提出したコード参照）

提出コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i< (n); ++i)
const int inf = 1001001001;

// dfs(depth first search)したいので、グローバル変数宣言
int V, E;
int dist[15][15]; // 問題の制約が15なので
int dp[1<<15][15]; // 「訪問頂点状態」と「現在の頂点」をメモ

// メモ化再帰(dfs)でDP更新
// arg s 訪れた頂点の状態（bitで管理）
// arg v 現在いる頂点
int dfs(int s, int v) {
  if (dp[s][v] >= 0) { // 更新済みのとき
    return dp[s][v];
  }

  // 答えになる条件を満たすとき
  if (s == (1<<V)-1 && v==0) {
    return dp[s][v] = 0;
  }
  int ans = inf;
  for (int u=0; u<V; u++) { 
    if (!(s >> u & 1)) { // まだ訪れていない頂点のとき
      // 再帰的にメモしながら探索
      ans = min(ans, dfs(s | 1 << u, u) + dist[v][u]);
    }
  }
  dp[s][v] = ans; // メモ
  return ans;
}

int main() {
  cin >> V >> E;
  // dp tableの初期化
  rep(i, 1<<15)rep(j, 15) dp[i][j] = -1;  
  // 距離の初期化
  rep(i, 15)rep(j, 15) dist[i][j] = inf;
  rep(i, E) {
    int s, t, d;
    cin >> s >> t >> d;
    dist[s][t] = d;
  } 
  // 全ての頂点を未訪問の状態からdfs開始（第一引数）
  // 全ての頂点を通るためどの頂点から始めても問題ないため  
  // 0から決め打ちしてはじめる（第二引数）
  int ans = dfs(0,0); 
  // 存在しなかったとき、「-1」を出力
  cout << (ans == inf ? -1 : ans) << endl;
  return 0;
}

ハイライトした部分がこの問題での肝要な部分。
DPの問題はこのdp tableの定義と更新方法さえわかってしまえば、それをforループor再帰で更新するだけなのだが、ここが本当に難しい。
再帰関数の引数も個人的にはなかなかトップダウンでこうすればいいということがわからないので、難しい部分だと思う。（なので、ハイライトしています。）
私はDPの典型問題、初見で解けたことがほとんどない。。

感想

DPの問題は余り悩んでも、解答が思いつかない気がする。
実装しながら試行錯誤するには特に再帰関数が入るとデバッグが面倒だし。。
個人的に他の人の解答を参考に自分なりのコメントや解答をつくるやりかたはストレスが少なくて良いと感じる。