leetcode279.完全平方数

和零钱兑换一样，只不过硬币是j*j<n算出来的

var memo []int
func numSquares(n int) int {
    coins:=make([]int,0)
    for j:=1;j*j<=n;j++{
        coins=append(coins,j*j)
    }
    memo=make([]int,n+1)
    for k,_:=range memo{
        memo[k]=6
    }
    return dp(coins,n)

}

func dp(coins []int,amount int) int{
    
   if  amount==0{
       return 0
   }
   if  amount<0{
       return -1
   }

   if memo[amount]!=6{
        return memo[amount]
    }

   res:=math.MaxInt
   for _,v:=range coins{
       sub:=dp(coins,amount-v)
       
       if sub==-1{
           continue
       }
       res=min(res,sub+1)
       if res!=math.MaxInt{
           memo[amount]=res
       }else{
           memo[amount]=-1
       }
   }
   return memo[amount]
}

func min(x,y int) int{
    if x>y{
        return y
    }
    return x
}