代码随想录day36 || 1049 最后一筐石头重量||， 494 目标和，474 一和零

1049 最后一块石头重量||

func lastStoneWeightII(stones []int) int {
	// 本题思路在于要想得到最小差，就要尽可能将石头分割为两堆相近的重量，然后转换为背包问题
	// dp[i] 表示容量i背包能装的石头总价值，其中重量和价值相等
	// 递推公式 dp[j] = max(dp[j], dp[j-w(i)] + v[i]) == max(dp[j], dp[j-s[i]]+s[i])
	// 初始化 dp[0] = 0
	// 遍历顺序，先正序物品， 后倒叙背包，原因在于递推公式依赖于上一层dp的状态推导，所以正序可能导致之前的元素被覆盖出现错误
	// print
	var sum, mid int
	for _, v := range stones{
		sum += v
	}
	mid = sum / 2

	var dp = make([]int, mid + 1)
	for i:=0; i<len(stones); i++ {
		for j:=mid; j>0; j-- {
			if j-stones[i] >= 0{
				dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
			}
		}
	}
	//fmt.Println(dp)
	return sum - 2*dp[mid]  // sum - dp[mid] 代表另一半石头的重量，然后两半相减得到的就是最小差
}

494 目标和

var path []int
var res int
var mutil = []int{-1, 1}
func findTargetSumWays(nums []int, target int) int {
	// 思考一下回溯办法
	//  回溯三部曲，参数以及返回值，终止条件，回溯遍历过程
	path = make([]int, 0)
	res = 0
	backTracking(nums, target, len(nums))
	return res
}

func backTracking(nums []int, target, length int ) {
	if len(path) == length{
		//fmt.Println(path)
		if sum(path) == target{
			res += 1
		}
		return
	}

	for i:=0; i<len(nums); i++{
		for _, v := range mutil{ // 每一个元素遍历两个，分别插入正数负数，结束时回溯
			path = append(path, v*nums[i])
			backTracking(nums[i+1: ], target, length )
			path = path[0: len(path) - 1]
		}
		break // !!!!!这里剪枝的目的是尽可能保障path长度为len(nums)，如果将首个元素去除的话，长度肯定小于len(nums)，所以剪枝
	}
}

func sum(n []int) int {
	var s int
	for _, v := range n {
		s += v
	}
	return s
}
// 回溯法超时
// 剪枝之后压线通过
	执行耗时:1897 ms,击败了5.04% 的Go用户
	内存消耗:2.2 MB,击败了69.39% 的Go用户

func findTargetSumWays(nums []int, target int) int {
	// 将数组划分为正数数组和负数数组 推导出正数数组 = （sum + target） / 2
	// dp[i][j] 代表尽可能装满容量为j的背包的方法数量
	// 递推：dp[i][j] = dp[i-1][j] + dp[i-1][j-w(j)] 代表不装j的方法数 + 装j的方法数
	// 初始化 dp[1][1] =1
	// 遍历顺序，随意
	// print
	var sum int
	for _, v := range nums {
		sum += v
	}
	if ( sum + target ) % 2 == 1 || float64(sum) < math.Abs(float64(target)) {
		return 0
	}

	mid := (sum + target) / 2
	var dp = make([][]int, len(nums) + 1)
	for idx, _ := range dp {
		dp[idx] = make([]int, mid + 1)
	}
	dp[0][0] = 1
	for i:=0; i<len(nums); i++ {
		for j:=0; j<=mid; j++{
			//fmt.Println(i+1, j, dp[i][j], dp[i][j-nums[i]])
			dp[i+1][j] = dp[i][j]
			if j - nums[i] >= 0 {
				dp[i+1][j] += dp[i][j-nums[i]]
			}
		}
	}
	//fmt.Println(dp)
	return dp[len(nums)][mid]
}

474 一和零

func findMaxForm(strs []string, m int, n int) int {
	// 此处难点在于二维的0-1背包
	// dp[i][j] 代表尽可能装满i个0，j个1的背包能获得的最大价值，由于价值等于数量*1 所以也是最大数量
	// 递推公式 dp[i][j] = max(dp[i][j], dp[i-x][j-y] + 1) // x,y分别代表字符0，1数量
	// 初始化全部为0
	// 遍历顺序，先正序物品，后倒叙背包，由于是滚动数组，所以dp数组依赖的是上一层的dp值，如果正序会覆盖上一层，所以不能正序
	// print

	var dp = make([][]int, m+1)
	for idx, _ := range dp{
		dp[idx] = make([]int, n+1)
	}

	for _, str := range strs {
		var x, y int
		for i:=0; i<len(str); i++ {
			if str[i] == '0'{
				x++
			}
			if str[i] == '1'{
				y++
			}
		}

		for i:=m; i>=x; i--{
			for j:=n; j>=y; j--{
				dp[i][j] = max(dp[i][j], dp[i-x][j-y] + 1)
			}
		}

	}
	//fmt.Println(dp)
	return dp[m][n]
}
func max (i, j int) int {
	if i>j{
		return i
	}
	return j
}