Today i try to solve this divisor game on leetcode, this problem is basic for dp programming, I solve this question using two methods, First one is without using any dynamic programming and second one by using dp.
Problem Statement:
Solution 1: Without DP with 0ms Runtime:
func divisorGame(n int) bool {
flag := true
for n>0{
n--
if flag{
flag = false
continue
}
flag= true
}
return flag
}
Solution2: with DP with 8ms:
func divisor(n int, lstofInt map[int]bool) bool {
if n == 1 {
return false
}
if lstofInt[n] {
return lstofInt[n]
}
for i := 1; i < n; i++ {
if n%i == 0 {
if !divisor(n-i, lstofInt) {
lstofInt[n] = true
return true
}
}
}
lstofInt[n] = false
return lstofInt[n]
}
func divisorGame(n int) bool {
lstOfInt := make(map[int]bool, 0)
return divisor(n, lstOfInt)
}
0 Comments