golang刷leetcode 技巧（29）硬币

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]
}