Leetcode 1025. 除数博弈（DAY 25）---- 动态规划学习期

原题题目

代码实现（首刷自解超时） ：(

bool gametest(int N,int role)
{
    if(N==1){
    if(role)return true;elsereturn false;}int temp = sqrt(N),i;for(i=1;i<=temp;i++){
    if(!(N%i)){
    if(!role){
    if(gametest(N-i,1))return true;}else{
    if(!gametest(N-i,0))return false;elsereturn true;}}}return false;
}bool divisorGame(int N){
    return gametest(N,0); 
}

代码实现（改进数据有记忆性）

bool gametest(int N,int role,int* judge)
{
    if(N==1){
    if(role)return true;elsereturn false;}int temp = sqrt(N),i;for(i=1;i<=temp;i++){
    if(!(N%i)){
    if(!judge[N-i])return false;if(!role){
    if(gametest(N-i,1,judge))return true;elsejudge[N-i] = 0;}else{
    if(!gametest(N-i,0,judge)){
    judge[N-i] = 0;return false;}elsereturn true;}}}return false;
}bool divisorGame(int N){
    int judge[N+2];memset(judge,1,sizeof(int) * N);return gametest(N,0,&judge); 
}