53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组，返回其最大和。
问：为什么不能用「选或不选 nums[i]」的思路做？
答：选或不选无法保证子数组是连续的。
- 选或不选适用于子序列问题（例如 0-1 背包问题）
- 对于子数组问题，更适合用「拼接」的思路，即如果 nums[i] 左边的子数组元素和是负的，就不用和左边的子数组拼在一起了。
300. 最长递增子序列 问：什么样的题目适合「选或不选」，什么样的题目适合「枚举选哪个」？ 答：我分成两类问题：
- 相邻无关子序列问题（比如 0-1 背包），适合「选或不选」。每个元素互相独立，只需依次考虑每个元素选或不选。
- 相邻相关子序列问题（比如本题），适合「枚举选哪个」。我们需要知道子序列中的相邻两个数的关系。对于本题来说，枚举 nums[i] 必选，然后枚举前一个必选的数，方便比大小。如果硬要用「选或不选」，需要额外记录上一个选的数的下标，算法总体的空间复杂度为 O(n 2 )，而枚举选哪个只需要 O(n) 的空间。
完全背包
dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i-1]]+1)
func coinChange(coins []int, amount int) int {
m, n := len(coins)+1, amount+1
dp := make([][]int, m)
for i := range m {
dp[i] = make([]int, n)
}
for j := range n {
dp[0][j] = math.MaxInt32
}
dp[0][0] = 0
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if coins[i-1] > j {
dp[i][j] = dp[i -1][j]
} else {
dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i-1]]+1)
}
}
}
if dp[m-1][n-1] > math.MaxInt32/2 {
return -1
}
return dp[m-1][n-1]
}