今日任务：

1. LeetCode70 爬楼梯
2. LeetCode322 零钱兑换
3. LeetCode279 完全平方数

资料来源：

1. 代码随想录 | LeetCode70 爬楼梯
2. 代码随想录 | LeetCode322 零钱兑换
3. 代码随想录 | LeetCode279 完全平方数

1 LeetCode70 爬楼梯

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

孩子们，我回来了。

这题的进阶版本一次爬多少阶是有1到m个台阶数可以选。也正如昨天所说，这题可以看作是一个求总和排列的问题。

go
func climbStairs(n int) int {
	array := []int{1, 2} // 对应进阶版的可选台阶 普通版的只有1和2 进阶版可以直接生成1到m的数组
	dpArray := make([]int, n + 1)
	dpArray[0] = 1
	for i := 1; i <= n; i++ {
		for _, j := range array {
			if i < j {
				continue
			}
			dpArray[i] += dpArray[i - j]
		}
	}
	return dpArray[n]
}

2 LeetCode322 零钱兑换

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

输入：coins = [2], amount = 3
输出：-1

输入：coins = [1], amount = 0
输出：0

对不起，我傻了，我初始化为-1然后排除了半天的各种情况，排除了半天最后才意识到设置一个不可能的最大值是可行的。

go
func coinChange(coins []int, amount int) int {
	if amount == 0 {
		return 0
	}
	dpArray := make([]int, amount + 1)
	for index := range dpArray {
		dpArray[index] = -1
	}
	for _, coin := range coins {
		if coin <= amount {
			dpArray[coin] = 1
		}
	}
	for _, coin := range coins {
		for i := coin; i <= amount; i++ {
			if dpArray[i - coin] == -1 { // 要找的上一个数字确定没有有效的组合
				continue
			}
			if dpArray[i - coin] != -1 { // 有有效的组合
				if dpArray[i] == -1 { // 开始初始化
					dpArray[i] = dpArray[i - coin] + 1
				} else { // 向更小的方向修改值
					dpArray[i] = min(dpArray[i], dpArray[i - coin] + 1)
				}
			}
		}
	}
	if dpArray[amount] == 0 {
		return -1
	}
	return dpArray[amount]
}

3 LeetCode279 完全平方数

吸取了上一道题的教训写的，效果显著。

go
func numSquares(n int) int {
	dpArray := make([]int, n + 1)
	for index := range dpArray {
		dpArray[index] = 10000
	}
	dpArray[0] = 0
	
	for i := 1; i <= n; i++ {
		for j := i * i; j <= n; j++ {
			dpArray[j] = min(dpArray[j], dpArray[j - (i * i)] + 1)
		}
	}
	return dpArray[n] // 这里是肯定有值的 最多最多的情况 那也就是1万个1相加么
}