为什么我没有做出这道算法题

Table of Contents

题目描述 #

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额的组合数量。

每种硬币的数量是无限的。

心路历程 #

简单的动态规划? #

找零钱问题是比较经典的动态规划问题，按照动态规划的思路一把梭应该就解出来了。

func find(coins []int, amount int) int {
  dp := make([]int, amount+1)    // dp[i]为总金额为i的组合的数量
	for i:=1; i <=amount ;i++ {
		for _, coin := range coins {
			if i >= coin {
				dp[i] += dp[i-coin]// dp[i]的组合数量为dp[i-coin]的组合数量之和
			}
		}
	}
	return dp[amount]
}

写完之后觉得不太对，dp没有做初始化，这样不管后边如何累加元素都是0，于是考虑将dp[0]设为1。带入代码中，当coin等于i时，说明这个硬币的面值就是目的金额，因此将对应的组合数量加1。所以将dp[0]设为1应该没问题。

func find(coins []int, amount int) int {
  dp := make([]int, amount+1)    // dp[i]为总金额为i的组合的数量
  dp[0] = 1
	for i:=1; i <=amount ;i++ {
		for _, coin := range coins {
			if i >= coin {
				dp[i] += dp[i-coin]// dp[i]的组合数量为dp[i-coin]的组合数量之和
			}
		}
	}
	return dp[amount]
}

大功告成！测一下。

func main() {
	fmt.Println(find([]int{1,2}, 4))
}

当硬币面值为1和2，总金额为4时应该有3中组合方式：

1+1+1+1
1+1+2
2+2

点击运行，结果输出为5。。。

果然有问题！

问题分析 #

这个状态转移方程dp[i] += dp[i-coin]看着不太对。

将for循环中的每次累加都打印下:

for _, coin := range coins {
    if i >= coin {
        dp[i] += dp[i-coin]
        fmt.Println(i, dp[i])
    }
}

输出：

1 1 // 当总金额为1时，只有一种组合方式: 1
2 1
2 2 // 当总金额为2时，有两种组合方式: 1+1, 2
3 2
3 3 // 当总金额为3时，有三种组合方式？
4 3
4 5

总金额为3时，组合方式应该是有两种，1+1+1, 1+2，为什么会有三种呢？

分析for循环，应该是这样：dp[3] = dp[1]+dp[2].

问题找到了：dp[2]中的组合方式包括dp[1]中的组合方式，即1+1包含了1.

这就很麻烦了。想要解决这个问题，就要标记dp中的每个元素对应的组合方式是否包含了另一个元素中的组合方式。

这个思路应该不对。

用普通人的思考方式解决问题 #

作为一个人类，是如何找到组合方式的总数的？

将硬币从小到大排列，每次选择最小的，然后选择次小的，穷尽这些组合方式，看有多少组合方式能够达到总金额（其实不需要从小到大排列，只需按照顺序依次选择硬币即可）。

func find2(coins []int, amount int) int {
	cnt := 0
	var dfs func(amount, i int)
	dfs = func(amount, i int) {
		if amount == 0 {
			cnt++
			return
		}
		if amount < 0 {
			return
		}
		for j := i; j < len(coins); j++ {
            dfs(amount-coins[j], j)
		}
	}
	dfs(amount, 0)
	return cnt
}

用上边的用力测试一下，通过了！

优化暴力算法 #

简单粗暴的缺点就是时间复杂度太高了，优化下。

dfs方法中对每个元素都要进行递归，直到amount为0，这个过程中会存在大量相同amount，可以将每个amount对应的组合数保存起来，这样下次再查询这个amount就不用再次递归。可以选用哈希表来保存。

func find2(coins []int, amount int) int {
	m := make(map[int]int)
	var dfs func(amount, i int) int
	dfs = func(amount, i int) int {
		if amount == 0 {
			return 1
		}
		if amount < 0 {
			return 0
		}
		if n, ok := m[amount]; ok {
			return n
		}
		cnt := 0
		for j := i; j < len(coins); j++ {
			cnt += dfs(amount- coins[j], j)
		}
		m[amount] = cnt
		return cnt
	}

	return dfs(amount, 0)
}

用之前的用例测试一下，发现输出为5，又遇到了和之前一样的问题！

找到&解决问题 #

上面的问题在于重复使用了一些组合，如何才能避免重复使用呢？

之前设置的"状态转移方程"是dp[i] += dp[i-coin]，这会造成重复使用子数组。

为了避免重复，我们可以按照硬币的使用与否来设置状态转移方程，对于第i个硬币，其面值为coin，凑齐金额为j的组合数为前i-1个硬币凑齐金额为j的组合数加上前i个硬币凑成金额为j-coin的组合数（即不需要第i个硬币就能凑齐j的组合数+恰好需要第i个硬币就能凑齐j的组合数）。这时，状态转移方程为dp[i][j] = dp[i-1][j] +dp[i][j-coin]

修改代码为

func find3(coins []int, amount int) int {
	dp := make([][]int, len(coins)+1) // dp[i][j]使用前i个硬币组成金额为j的组合数
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, amount+1)
	}
	// dp初始化 使用前i个硬币组成金额为0的组合数为1
	for i:= 0; i <= len(coins); i++ {
		dp[i][0] = 1
	}

	for i := 1; i <= len(coins); i++ {
        coin := coins[i-1]
		for j := 1; j <= amount; j++ {
			if j >= coin {
				dp[i][j] = dp[i-1][j] + dp[i][j-coin]
			}else {
				dp[i][j] = dp[i-1][j]
			}
		}
	}
	return dp[len(coins)][amount]
}

在嵌套循环中，求dp[i][j]时，每次都会加上dp[i-1][j]，因此可以压缩dp数组——去掉第一个维度，此时dp[i]表示凑齐金额为j的组合数（因为第一个维度中，第i个元素只依赖第i-1个元素，因此可以通过累加来将这个维度的数组压缩成一个元素）。

func find4(coins []int, amount int) int {
	dp := make([]int, amount+1) // dp[i]:组成金额为i的组合数
	// dp初始化 组成金额为0的组合数为1
	dp[0] = 1
	for i := 1; i <= len(coins); i++ {
		for j := 1; j <= amount; j++ {
			if j >= coins[i-1] {
				dp[j] += dp[j-coins[i-1]]
			}
		}
	}
	return dp[amount]
}

优化遍历coins的代码：

func find5(coins []int, amount int) int {
	dp := make([]int, amount+1) // dp[i]:组成金额为i的组合数
	// dp初始化 组成金额为0的组合数为1
	dp[0] = 1
	for _, coin := range coins {
		for j := 1; j <= amount; j++ {
			if j >= coin {
				dp[j] += dp[j-coin]
			}
		}
	}
	return dp[amount]
}

再次回顾之前错误的代码：

func find(coins []int, amount int) int {
  dp := make([]int, amount+1)    // dp[i]为总金额为i的组合的数量
  dp[0] = 1
	for i:=1; i <=amount ;i++ {
		for _, coin := range coins {
			if i >= coin {
				dp[i] += dp[i-coin]// dp[i]的组合数量为dp[i-coin]的组合数量之和
			}
		}
	}
	return dp[amount]
}

发现两者的区别只是嵌套循环的顺序不一致。

先遍历amount，再遍历coins，得到的是一种“排列数”（能够重复使用之前的子组合，类比爬楼梯问题）。
先遍历coins，再遍历amount，得到的是一种“组合数”（不会重复使用之前的子组合）

总结 #

动态规划掌握的还不熟练。
当使用“经验”没有办法解决问题时，可以先想想普通人的解决步骤（大部分情况下是暴力算法），然后通过代码复现。
多思考多做总结，单纯的解决问题没有意义（以前做过的题竟然还是做不出来）

后记 #

组合数意味着什么呢，意味着顺序是可以不同的，比如{1,2,1}和{1,1,2}是相同的组合。为了避免这种重复，我们先按照硬币的顺序遍历。

再看下先遍历金额的代码：

func find(coins []int, amount int) int {
  dp := make([]int, amount+1)
  dp[0] = 1
	for i:=1; i <=amount ;i++ {
		for _, coin := range coins {
			if i >= coin {
				dp[i] += dp[i-coin]
			}
		}
	}
	return dp[amount]
}

结果是能够组成amount的硬币的排列数。为什么要先遍历金额呢？或者说我们能为先遍历金额赋予什么意义呢？类比先遍历硬币，我们可以认为，先遍历金额能够避免金额的重复。

这个解释是合理的，毕竟如果之前遍历过金额a，后续再次遍历金额a，那么dp[a]所代表的金额为a的排列数就会是错的。

所以我们可以得出结论：在bp的双循环中，外层循环遍历的是不能重复的元素。

参考 #

零钱兑换II和爬楼梯问题到底有什么不同？