题目：70. 爬楼梯
思路：
除了dp[i] = dp[i-1] + dp[i-2]还可以用完全背包的方法，可以放无数个1或者2，看有多少种排列(先背包后物品)
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
代码：
func climbStairs(n int) int {
dp := make([]int, n+1)
dp[0] = 1
m := 2
for j := 1; j <= n; j++ { //先遍历背包
for i := 1; i <= m; i++ { //再遍历物品
if j >= i {
dp[j] += dp[j-i]
}
}
}
return dp[n]
}
参考：
题目：322. 零钱兑换
思路：
这个题排列还是组合都无所谓，最少的硬币数就行。
代码：
func coinChange(coins []int, amount int) int {
dp := make([]int, amount + 1)
for i:=1; i<len(dp); i++ {
dp[i] = math.MaxInt32
}
for i := 0; i < len(coins); i++ {
for j := coins[i]; j <= amount; j++ {
if dp[j - coins[i]] != math.MaxInt32 {
dp[j] = min(dp[j], dp[j-coins[i]]+1)
}
}
}
if dp[amount] == math.MaxInt32 {
return -1
}
return dp[amount]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
参考：
题目：279. 完全平方数
思路：
和上一个题一样啊喂
代码：
func numSquares(n int) int {
dp := make([]int, n+1)
for i := 1; i < len(dp); i++ {
dp[i] = math.MaxInt32
}
for i := 0; i <= n; i++ {
for j := 1; j * j <= i; j++ {
dp[i] = min(dp[i - j * j] + 1, dp[i])
}
}
return dp[n]
}
func min(a,b int)int {
if a < b {
return a
}
return b
}