代码随想录day 38 || 322 零钱兑换，279 完全平方数，139 单词拆分

322 零钱找还

func coinChange(coins []int, amount int) int {
	// 装满，并且硬币无限，可以类比完全背包问题
	// dp[i][j] 表示前i个物品装满容量为j的背包所需要的最少物品数量
	// 递推公式 dp[i][j] = min(dp[i-1][j], dp[i][j-w(i)]+1) // 不装物品i的物品数量，装物品i的物品数量
	// 初始化 dp[0][0] = 0, 其他数值为math.minint
	// 遍历顺序，本题没有要求全排列或者全组合，所以用了二维，二维顺序是无所谓的，但是习惯还是先物品后背包
	// print
	var dp = make([][]int, len(coins) + 1)
	for idx, _ := range dp {
		dp[idx] = make([]int, amount + 1)
		for j := range dp[idx] {
			dp[idx][j] = amount + 1 // 用来表示一个无法凑成的最大金额，方便在min操作时取到正确的最小值
		}
	}
	dp[0][0] = 0
	for i:=0; i<len(coins); i++{
		for j:=0; j<=amount; j++{
			if j-coins[i] >= 0 { // 要满足剩余背包容量大于等于0
				dp[i+1][j] = min(dp[i][j], dp[i+1][j-coins[i]]+1)
			}else {
				dp[i+1][j] = dp[i][j]
			}
		}
	}

	//fmt.Println(dp)
	if dp[len(coins)][amount] > amount {
		return -1
	}
	return dp[len(coins)][amount]
}

func min(x,y int )int {
	if x < y{
		return x
	}
	return y
}

// 本题思路好找，难点在于取最小值的时候是否能够想到将dp数组初始化为一个比较大的数，而不是0

func coinChange(coins []int, amount int) int {
	// 装满，并且硬币无限，可以类比完全背包问题
	// dp[j] 表示装满容量为j的背包所需要的最少物品数量
	// 递推公式 dp[j] = min(dp[j], dp[j-w(i)]+1) // 不装物品i的物品数量，装物品i的物品数量
	// 初始化 dp[0] = 0, 其他数值为amount + 1, 这里表示如果全是1来组成amount，需要amount个1，这已经时需要的最大数量，那我设置amount+1，就是要比最大值还要大
	// 遍历顺序，本题没有要求全排列或者全组合，完全背包一位数组按照习惯先正序物品，后正序背包
	// print
	var dp = make([]int, amount + 1)
	for i, _ := range dp {
		dp[i] = amount + 1
	}
	dp[0] = 0
	for i:=0; i<len(coins); i++{
		for j:=0; j<=amount; j++{
			if j-coins[i] >= 0 { // 要满足剩余背包容量大于等于0
				dp[j] = min(dp[j], dp[j-coins[i]]+1)
			}
		}
	}

	//fmt.Println(dp)
	if dp[amount] > amount {
		return -1
	}
	return dp[amount]
}

func min(x,y int )int {
	if x < y{
		return x
	}
	return y
}

279 完全平方数

func numSquares(n int) int {
	// 完全背包
	// dp[j] 表示装满容量j的背包需要最少完全平方数
	// 递推 dp[j] = min(dp[j], dp[j-i^2] + 1)
	// dp[0] = 0  其他初始化成为n+1
	// 先正序物品，后正序背包 背包0->n 物品0->n开方+1
	// print

	var dp = make([]int, n+1)
	s := int(math.Sqrt(float64(n))) + 1
	for idx, _ := range dp {
		dp[idx] = n+1
	}
	dp[0] = 0
	for i:=1; i<=s; i++ {
		for j:=i*i; j<=n; j++{
			dp[j] = min(dp[j], dp[j-i*i]+1)
		}
	}
	fmt.Println(dp)
	return dp[n]
}

139 单词拆分

func wordBreak(s string, wordDict []string) bool {
	// 本题可以联想到完全背包问题，但是难点在于，1 dp数组含义 2 递推公式 3 遍历顺序
	// dp[j] 表示前j个字母能够呗字典中的单词拼出
	// 递推公式，对于每一个单词  dp[j] = dp[j-len()] && true  表示本单词+目标-本单词长度剩余的单词能否被拼出
	// 遍历顺序，字典可能被多次使用，并且顺序可以颠倒，所以时全排列，先正序背包，后正序物品
	// print

	m := minlength(wordDict)
	if len(s) < m {
		return false
	}
	var dp = make([]bool, len(s) + 1)
	dp[0] = true
	for j:=m-1; j<len(s); j++ {
		for i:=0; i<len(wordDict); i++{
			diff := j-len(wordDict[i])+1
			if diff >= 0 && s[diff: j+1] == wordDict[i]{
				dp[j+1] = dp[diff]
			}
			if dp[j+1] == true {
				break
			}
		}
	}

	//fmt.Println(dp)
	return dp[len(s)]
}

func minlength(dict []string) int {
	var m int = math.MaxInt
	for _, v := range dict{
		if len(v) < m {
			m = len(v)
		}
	}
	return m
}