動的計画法と高度なグラフ問題

動的計画法

重なり合う部分問題の結果を保存して再利用します。状態、遷移、初期値、答えの位置を明確にします。

最小コイン枚数

dp[x]を金額xを作る最小枚数とします。最後に額面cを使うならdp[x-c]+1です。

fn min_coins(a:usize,coins:&[usize])->Option<usize>{
 let inf=a+1;let mut d=vec![inf;a+1];d[0]=0;
 for x in 1..=a{for &c in coins{if c>0&&c<=x{d[x]=d[x].min(d[x-c]+1);}}}
 if d[a]==inf{None}else{Some(d[a])}
}

時間O(XC)、空間O(X)です。制約に対して許容できるか確認します。グラフではBFS、Dijkstra、Union-Findなどを問題の構造に応じて選びます。

演習：最小コイン枚数