還暦爺がAtCoderにPascalで挑戦② DP１問解きました。

おさらい

先輩Coderの方の記事を見るとやはり過去問を順次解いていくのが王道の様です。
しかしながらじっくり勉強するのが子供の頃から苦手な私、
なかなかモチベーションが湧きません。
ということでコンテストで取り組んだけど解けなかった問題を時間をかけて
おさらいすることにしました。
コンテスト中はそれなりに真面目に考えているので初見の問題よりは
頭に残っている分考えやすい様に思います。
ちゃんと理解しないで形だけ覚えても応用が利かないので腑に落ちるまで
考えてみます。
今回は

に取り組んでみました。コンテスト中は全ケースの組み合わせじゃTLE確実だし
と悩んだ結果脱落。
解説を見るとこの問題はDP（動的計画法）で解けるとのこと。
DPとはなんじゃらほいとググっていくつかの記事を見てみました。
分かった様な分からないような…
最小範囲のケースを解決してそれを足場にどんどん範囲を拡げていく感じ？

この問題の場合はまず１種類の硬貨で払える金額のブーリアン配列を作っていって
その配列の結果に次の種類の硬貨で払える金額を加えていく感じです。
最終的に dp[n][x] の値がtrueになっていれば払えることになります。

var n,x,i,j,v,k : integer;
    a,b : array of integer;
    dp : array[0..50,0..10000] of boolean;

begin
  read(n,x);
  setlength(a,n+1);  // 1オリジンで使うため+1しておく
  setlength(b,n+1);  // a[0],b[0]は使わない
  for i := 0 to 50 do
    for j := 0 to 10000 do
      dp[i][j] := false;
  dp[0][0] := true;
  for i := 1 to n do
    read(a[i],b[i]);
// 硬貨の種類分繰り返し
  for i := 1 to n do
  begin
    // 硬貨の枚数分繰り返し
    for j := 0 to b[i] do
    begin
      v := a[i]*j;  // その枚数での金額
      dp[i][v] := true; 
      // １つ前の結果に足していく
      for k := 0 to x-v do
        if dp[i-1][k] then 
          dp[i][k+v] := true;
    end;
  end;
  // 最終結果判定
  if dp[n][x] then
    writeln('Yes')
  else
    writeln('No');
 
end.

無事ACとなりました。
次回同類の問題が出た時にうまく応用できるかは自信ないけど。
とりあえずは めでたしめでたし。