The main observation is that at any time you would want to go to a state where the second player wins. So you check whether there exists any reachable state where the second player wins. if there is, that state is a first player win, if there isn’t, then it’s a second player win state.
Then finish off with recursion and memoisation.
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
long long int p=1e9 +7;
int n;
int moves[100];
int ans[100007]={0};
int solve(int k){
if(ans[k]){
return ans[k];
}
for(int i=0;i<n;i++){
if(k>=moves[i]){
if(solve(k-moves[i])==2){
ans[k]=1;
return ans[k];
}
}
}
ans[k]=2;
return ans[k];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int k;
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>moves[i];
}
ans[0]=2;
if(solve(k)==1){
cout<<"First";
}
else{
cout<<"Second";
}
}
2 Likes
https://atcoder.jp/contests/dp/submissions/14689730
Implemented via iterative dp.
Remove my commented lines in solve function then you can get your solution via top-down(recursive) way also.