再帰の力を信じる

はじめに

longrunさんが立ててくださった＜EDPC+αを再帰で解く＞というバチャに参加してみました。

https://kenkoooo.com/atcoder/#/contest/show/2c951dcc-fd87-4369-ac6e-9ed5b91ce271

学んだこと

そもそもDPの問題が再帰で解けるという感覚がなかったのですが，なるほどやっていることは同じです。

初期値を適切に決めることと，遷移式を正しく建てることの２つを意識しつつ，再帰の鬼門の爆発を防ぐため，メモ化をします。

再帰は再帰関数に投げたあとどうなるのか不安がつきまとうので，苦手意識がありましたが，再帰の力を信じて投げてやるとしっかり応えてくれます。

－　再帰を信じるものは救われる　－＜競プロ格言＞

まだ数問悩んだだけですが，再帰の理解もDPの理解も格段に深まった気がします。

ナップサック問題　提出コード

#include <bits/stdc++.h>
using namespace std;

int n;
long long W;
long long w[110];
long long v[110];
long long memo[110][100100];
long long saiki(long long x,long long y){
  if(memo[x][y] != 0) return memo[x][y];
  if(x==0) return 0;
  //1番目以降
  long long ans=0; 
  if(y>=w[x-1]){
    ans=max(saiki(x-1,y),saiki(x-1,y-w[x-1])+v[x-1]);
  }
  else{
    ans=saiki(x-1,y);
  }
  memo[x][y]=ans;
  return ans;
}

signed main(){
  cin>>n;
  cin>>W;
  for(int i=0;i<n;i++) cin>>w[i]>>v[i];
  cout<<saiki(n,W)<<endl;
  return 0;
}