Почему алгоритм с указателями работает быстрее?

Question

Всем привет. Может кто помочь с задачей? Есть два решения, первое мое, оно не проходило по времени на тесте: coins=[186, 419, 83, 408], amount=6249. Второе подглядел в решениях.

Собственно все чем они отличаются это типом данных в dp, в моем решение это int, во втором указатели на int. Первое валится с timelimit, второе успешно проходит, при этом разница в скорости на выше приведенном тесте значительная. Первое решение отрабатывает за 30+ секунд, второе < секунды. Не могу понять почему такая разница в скорости. Буду благодарен за помощь

Первое:


func coinChange(coins []int, amount int) int {
 dp := make([]int, amount+1)
 for i := range dp {
  dp[i] = math.MaxInt32
 }
 var r func(need int) int
 r = func(need int) int {
  if need < 0 {
   return math.MaxInt32
  }
  if need == 0 {
   return 0
  }
  if dp[need] != math.MaxInt32 {
   return dp[need]
  }
  needCoins := math.MaxInt32
  for _, c := range coins {
   needCoins = min(needCoins, 1+r(need-c))
  }
  dp[need] = needCoins
  return needCoins
 }

 ans := r(amount)
 if ans == math.MaxInt32 {
  return -1
 }
 return ans
}

Второе:


func coinChange(coins []int, amount int) int {
 dp := make([]*int, amount+1)
 var r func(need int) int
 r = func(need int) int {
  if need < 0 {
   return math.MaxInt32
  }
  if need == 0 {
   return 0
  }
  if dp[need] != nil {
   return *dp[need]
  }
  needCoins := math.MaxInt32
  for _, c := range coins {
   needCoins = min(needCoins, 1+r(need-c))
  }
  dp[need] = &needCoins
  return needCoins
 }

 ans := r(amount)
 if ans == math.MaxInt32 {
  return -1
 }
 return ans
}

Answer 1

Разница в том, как вы сохраняете информацию о неразрешимой сумме.

В случае указателей:
- вы записываете dp[unsolvable] = &math.MaxInt32,
- когда в процессе перебора снова появляется unsolvable, вы проверяете dp[unsolvable] != nil -- такое значение не nil, и r возвращает сохраненный результат.
В случае целых чисел:
- вы записываете dp[unsolvable] = math.MaxInt32
- когда в процессе перебора появляется снова появляется unsolvable, вы проверяете dp[unsolvable] != math.MaxInt32, но кэшированное значение равно как раз math.MaxInt32, и r снова пытается найти разложение unsolvable на сумму монет.

В варианте с целыми числами вам нужно инициализировать dp числом, которое точно не появится как возвращаемые значения r, например -1:

func coinChange2(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = -1
    }
    var r func(need int) int
    r = func(need int) int {
        if need < 0 {
            return math.MaxInt32
        }
        if need == 0 {
            return 0
        }
        if dp[need] >= 0 {
            return dp[need]
        }
        needCoins := math.MaxInt32
        for _, c := range coins {
            needCoins = min(needCoins, 1+r(need-c))
        }
        dp[need] = needCoins
        return needCoins
    }

    ans := r(amount)
    if ans == math.MaxInt32 {
        return -1
    }
    return ans
}

Вариант с указателями: 0.000686374 секунд

Вариант coinChange2: 0.000269819 секунд

БЛОГ НА HUSL

Почему алгоритм с указателями работает быстрее?

Ответы (1 шт):