溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

golang刷leetcode技巧之如何解決硬幣問題

發(fā)布時(shí)間：2021-12-16 09:04:00 來源：億速云 閱讀：175 作者：小新 欄目：大數(shù)據(jù)

小編給大家分享一下golang刷leetcode技巧之如何解決硬幣問題，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

硬幣。給定數(shù)量不限的硬幣，幣值為25分、10分、5分和1分，編寫代碼計(jì)算n分有幾種表示法。(結(jié)果可能會(huì)很大，你需要將結(jié)果模上1000000007)

示例1:

 輸入: n = 5

 輸出：2

 解釋: 有兩種方式可以湊成總金額:

5=5

5=1+1+1+1+1

示例2:

 輸入: n = 10

 輸出：4

 解釋: 有四種方式可以湊成總金額:

10=10

10=5+5

10=5+1+1+1+1+1

10=1+1+1+1+1+1+1+1+1+1

說明：

注意:

你可以假設(shè)：

0 <= n (總金額) <= 1000000

解題思路：

1，注意和上一篇，爬樓梯的相似點(diǎn)和區(qū)別

面額dp[i]!=sum(dp[i-coins[j]])

因?yàn)槿绻鹍p[i-coins[j]]全部由面額為coins[j]的硬幣組成，那么dp[i]應(yīng)該是1 而不是累加。爬樓梯需要累加

2，狀態(tài)轉(zhuǎn)移方程

令 dp[i][j] 為遍歷到當(dāng)下i這個(gè)硬幣時(shí)，組成金額 j 的方法數(shù)目，有兩種可能性：

（1）當(dāng)前這個(gè)硬幣沒有取，dp[i][j]=dp[i-1][j]；

（2）當(dāng)前這個(gè)硬幣取了，dp[i][j]=dp[i][j-coins[i]]

最后的結(jié)果是兩者的和

如果j<dp[i][j-coins[i]],則，不應(yīng)該計(jì)入（2）

注意：硬幣面值也需要升序

代碼實(shí)現(xiàn)

func waysToChange(n int) int {    coins:=[]int{1,5,10,25}  /*  dp:=make([]int,n+1)  dp[0]=1  for i:=1;i<n+1;i++{      for j:=0;j<len(coins);j++{          if i>=coins[j]{          dp[i]=(dp[i]+dp[i-coins[j]])%1000000007          }      }  }  //類似邁臺(tái)階，當(dāng)時(shí)這里有個(gè)問題，如果上一個(gè)結(jié)果是用的1分面額，從上一個(gè)面額到當(dāng)前面額還是用1分加的，這種情況不能算  return dp[n]  */
  /**  令 dp[i][j] 為遍歷到當(dāng)下這個(gè)硬幣時(shí)，組成金額 j 的方法數(shù)目有兩種可能性（1）當(dāng)前這個(gè)硬幣沒有取，dp[i][j]=dp[i-1][j]；（2）當(dāng)前這個(gè)硬幣取了，dp[i][j]=dp[i][j-coins[i]]。最后的結(jié)果是兩者的和將狀態(tài)轉(zhuǎn)移方程翻譯成代碼，并處理邊界條件  */   dp:=make([][]int, 4)  for i:=0;i<4;i++{      dp[i]=make([]int,n+1)  }  for i:=0;i<n+1;i++{      dp[0][i]=1  }  for i:=0;i<4;i++{      dp[i][0]=1  }
  for i:=1;i<4;i++{      for j:=1;j<=n;j++{          if j>=coins[i]{             dp[i][j]=(dp[i-1][j]+dp[i][j-coins[i]])%1000000007          }else{             dp[i][j]=dp[i-1][j]           }      }  } return dp[3][n]}

看完了這篇文章，相信你對(duì)“golang刷leetcode技巧之如何解決硬幣問題”有了一定的了解，如果想了解更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手