お嬢様系女子校生の日記

もう一度、、もう一度チャンスを、、、

復習dfs

基礎的な部分を補強するためにいつも使っている本のかなり前半の方を復習していた。確か、当時車校の受付前の机で勉強していた内容だったかと思う。んで見てみたらよ。方針は全く間違ってないけど、どうもテストケースが合わない。何をミスしてるのかといじってみたら思ってもなかったところが間違ってた。

int n;
int a[21];
int k;
bool dfs(int i,int mokuhyou){
//下の行のi==nをi==n-1にしてた。
        if(i==n) return mokuhyou==0;
        return dfs(i+1,mokuhyou-a[i])||dfs(i+1,mokuhyou);
}

int main(){
        cin>>n;
        for(int i=0; i<n; i++) {
                cin>>a[i];
        }
        cin>>k;
        if(dfs(0,k)) {
                cout<<"Yes"<<endl;
        }else{
                cout<<"No"<<endl;
        }
}

全く気にしてなかった所だったので当時の自分は何をしていたのかと思いながらも、復習は大事だなぁと思った。考え方としてはi==0の段階ではまだ何も配列aから取り出そうとしていない初期状態である事を意識し、i==1以降でaから取り出すor取り出さないをdfsしていく事を考える。従って、いつもの癖でiの範囲を0からn-1までとしやすいが、それは違っていてiは0からnまでの範囲で動かさなければならない。