leetcode 322 零钱兑换

bobo老师您好，我在做leetcode322题的时候，有两个问题一直困扰着我，我也尝试了打印出来和画图，还是想不通。老师能帮我解答解答吗。这道题我采用的是递归+记忆化搜索的思路。

我的问题

• 问题一：这种涉及到求最大值最小值的递归，采用print方法适合来debug吗？如果适合，print应该放在哪些位置，需要打印出哪些值，能够让我更好的看清程序的运行过程呢？
• 问题二：下面的版本一中的res = min(res, self.dfs(coins, amount-coins[i], count+1))和版本二中的res = min(res, 1+self.dfs(coins, amount-coins[i]))我分析起来觉得他们的效果一样特别是1+self.dfs()和递归过程中count+1最后再return count，我的理解这两种最后返回的值应该是一样的。但是为什么却得到不同的结果呢？

我的代码

• 版本一： 递归+记忆化搜索的方法(此方法答案错误了)

class Solution:
	def coinChange(self, coins: List[int], amount: int) -> int:
		self.memo = [-1]*(amount+1)
		res = self.dfs(coins, amount, 0)
		if res == float('inf'):
			return -1
		else:
			return res

	def dfs(self, coins, amount, count):
		if amount < 0:
			return float('inf')

		if amount == 0:
			return count

		if self.memo[amount] != -1:
			return self.memo[amount]
			
		res = float('inf')
		for i in range(len(coins)):
			res = min(res, self.dfs(coins, amount-coins[i], count+1))
		
		self.memo[amount] = res
		return res

• 版本二：递归+记忆化搜索的方法(accepted)

class Solution:
	def coinChange(self, coins: List[int], amount: int) -> int:
		self.memo = [-1] * (amount+1)
		res = self.dfs(coins, amount)
		
		if res == float('inf'):
			return -1
		else:
			return res
	
	def dfs(self, coins, amount):
		if amount == 0:
			return 0

		if amount < 0:
			return float('inf')

		if self.memo[amount] != -1:
			return self.memo[amount]

		res = float('inf')
		for i in range(len(coins)):
			res = min(res, 1+self.dfs(coins, amount-coins[i]))
			
		self.memo[amount] = res
		return res

• 我的print方法(但是通过这样设置print我还是不能很好的看出程序运行过程)

class Solution:
	def coinChange(self, coins: List[int], amount: int) -> int:
		if amount == 0:
			return 0

		res = self.dfs(coins, amount, 0)
		if res == float('inf'):
			return -1
		else:
			return res

	def dfs(self, coins, amount, depth):
		if amount == 0:
			return 0

		if amount < 0:
			return float('inf')

		res = float('inf')
		for i in range(len(coins)):
			print(self.gen_depth(depth), res)
			res = min(res, 1+self.dfs(coins, amount-coins[i], depth+1))
		
		return res
		
	def gen_depth(self, depth):
		string = ''
		for i in range(depth):
			string += '-'
		return string