主页 / user-579959

Mr Babls's questions

Martin Hope
Mr Babls
Asked: 2024-01-10 03:43:01 +0000 UTC
  • 8

大家好。任何人都可以帮助完成任务吗？有两个解决方案，第一个是我的，它没有通过测试时间：coins=[186, 419, 83, 408]，amount=6249。我注意到的第二件事是决策。

实际上，它们唯一的区别在于 dp 中的数据类型，在我的解决方案中它是 int，在第二个中有指向 int 的指针。第一个在时间限制下失败，第二个成功通过，上述测试的速度差异很大。第一个解决方案需要 30 秒以上，第二个解决方案需要 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
}
алгоритм