golang刷leetcode技巧之如何解决硬币问题

小编给大家分享一下golang刷leetcode技巧之如何解决硬币问题,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!

硬币。给定数量不限的硬币,币值为25分、10分、5分和1分,编写代码计算n分有几种表示法。(结果可能会很大,你需要将结果模上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

说明:

注意:

你可以假设:

0 <= n (总金额) <= 1000000

解题思路:

1,注意和上一篇,爬楼梯的相似点和区别

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

因为如果dp[i-coins[j]]全部由面额为coins[j]的硬币组成,那么dp[i]应该是1 而不是累加。爬楼梯需要累加

2,状态转移方程

令 dp[i][j] 为遍历到当下i这个硬币时,组成金额 j 的方法数目,有两种可能性:

(1)当前这个硬币没有取,dp[i][j]=dp[i-1][j];

(2)当前这个硬币取了,dp[i][j]=dp[i][j-coins[i]]

最后的结果是两者的和

如果j<dp[i][j-coins[i]],则,不应该计入(2)

注意:硬币面值也需要升序

代码实现

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          }      }  }  //类似迈台阶,当时这里有个问题,如果上一个结果是用的1分面额,从上一个面额到当前面额还是用1分加的,这种情况不能算  return dp[n]  */
 /**  令 dp[i][j] 为遍历到当下这个硬币时,组成金额 j 的方法数目有两种可能性(1)当前这个硬币没有取,dp[i][j]=dp[i-1][j];(2)当前这个硬币取了,dp[i][j]=dp[i][j-coins[i]]。最后的结果是两者的和将状态转移方程翻译成代码,并处理边界条件  */   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]}

看完了这篇文章,相信你对“golang刷leetcode技巧之如何解决硬币问题”有了一定的了解,如果想了解更多相关知识,欢迎关注亿速云行业资讯频道,感谢各位的阅读!

原创文章,作者:奋斗,如若转载,请注明出处:https://blog.ytso.com/tech/opensource/223978.html

(0)
上一篇 2022年1月7日 04:42
下一篇 2022年1月7日 04:42

相关推荐

发表回复

登录后才能评论