代码随想录：动态规划

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func fib(n int) int {
    if n <= 0 {
       return 0
    }
    if n <= 2 {
       return 1
    }
    dp := make([]int, n+1)
    dp[0], dp[1] = 0, 1
    for i := 2; i <= n; i++ {
       dp[i] = dp[i-1] + dp[i-2]
       //fmt.Printf("%d ", dp[i])
    }
    return dp[n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func fib(n int) int {
    if n <= 0 {
       return 0
    }
    if n <= 2 {
       return 1
    }
    dp := make([]int, 2)
    sum := 0
    dp[0], dp[1] = 0, 1

    for i := 2; i <= n; i++ {
       sum = dp[0] + dp[1] // 保存dp[0]和dp[1]的和
       dp[0] = dp[1]       // 将dp[0]后移1位
       dp[1] = sum         // 将dp[1]设置为前两个位置的和
       //fmt.Printf("%d ", sum)
    }
    return sum
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func climbStairs(n int) int {
    if n <= 2 {
       return n
    }
    methodCount := make([]int, 3)
    // 初始条件：n=1时，methodCount=1，n=2时，methodCount=2
    methodCount[1] = 1
    methodCount[2] = 2
    methodSum := 0
    for i := 3; i <= n; i++ {
       methodSum = methodCount[1] + methodCount[2] // 记录前两个位置的和
       methodCount[1] = methodCount[2]             // 后移1位置
       methodCount[2] = methodSum                  // 将2位置置为前两个位置的和
       //fmt.Printf("%d ", methodSum)
    }
    return methodSum
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func minCostClimbingStairs(cost []int) int {
    if len(cost) <= 1 {
       return 0
    }
    minCost := make([]int, len(cost)+1) // minCost数组的长度比cost数组多1个
    minCost[0] = 0
    minCost[1] = 0
    i := 2
    for ; i < len(cost); i++ {
       minCost[i] = min(minCost[i-1]+cost[i-1], minCost[i-2]+cost[i-2])
       //fmt.Println(i, minCost[i])
    }
    minCost[i] = min(minCost[i-1]+cost[i-1], minCost[i-2]+cost[i-2]) // 由于需要跳到的位置为cost数组长度的后一个位置，所以这里还需要计算跳到最后一个位置需要的最小步数
    return minCost[i]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := 0; i < m; i++ {
       dp[i] = make([]int, n)
    }
    for i := 0; i < m; i++ {
       dp[i][0] = 1 // 路径数为1
    }
    for j := 0; j < n; j++ {
       dp[0][j] = 1 // 路径数也为1
    }
    for i := 1; i < m; i++ { // i，j都从1开始
       for j := 1; j < n; j++ {
          dp[i][j] = dp[i-1][j] + dp[i][j-1]
       }
    }
    return dp[m-1][n-1]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m := len(obstacleGrid)                                      // 行数
    n := len(obstacleGrid[0])                                   // 列数
    if obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1 { // 剪枝策略：当起始位置或终止位置为障碍物时，直接返回0
       return 0
    }
    dp := make([][]int, m)
    for i := 0; i < m; i++ {
       dp[i] = make([]int, n)
    }
    for i := 0; i < m && obstacleGrid[i][0] == 0; i++ { // 当遇到obstacleGrid值为1时，置1操作停止
       dp[i][0] = 1
    }
    for j := 0; j < n && obstacleGrid[0][j] == 0; j++ {
       dp[0][j] = 1
    }
    for i := 1; i < m; i++ {
       for j := 1; j < n; j++ {
          if obstacleGrid[i][j] == 0 { // 添加当前位置不是障碍物的条件
             dp[i][j] = dp[i-1][j] + dp[i][j-1]
          }
       }
    }
    return dp[m-1][n-1]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func integerBreak(n int) int {
    dp := make([]int, n+1) // 多了一个0元素
    dp[0], dp[1], dp[2] = 0, 0, 1
    for i := 3; i <= n; i++ { // i从3开始
       for j := 1; j <= i/2; j++ { // j最大拆分为二分之i（因为i拆分为两个相等的数，乘积最大），再往上就没有任何意义了
          dp[i] = max(dp[i], max(j*(i-j), j*dp[i-j]))
       }
    }
    return dp[n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func numTrees(n int) int {
    dp := make([]int, n+1) // 包含0元素
    dp[0], dp[1] = 1, 1
    for i := 2; i <= n; i++ {
       tempSum := 0 // 当i变化时，将tempSum重置为0
       for j := 0; j <= i-1; j++ {
          tempSum += dp[j] * dp[i-j-1] // 累加总共的构造方法
       }
       dp[i] = tempSum
    }
    return dp[n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func backpackMaxValue(n, w int, weight, value []int) int {
    dp := make([][]int, n) // 行表示背包的物品数量
    for i := 0; i < n; i++ {
       dp[i] = make([]int, w+1) // 列表示背包容量，这里加1是因为还有容量为0的情况
    }
    // dp数组的初始值都为0
    for j := 0; j <= w; j++ { // j表示背包容量
       if j >= weight[0] { // 背包容量可以容纳物品0
          dp[0][j] = value[0]
       }
    }
    for i := 1; i < n; i++ { // 先遍历物品
       for j := 1; j <= w; j++ { // 再遍历背包
          if j < weight[i] { // 放入物品i超出背包的容量了，就只能不放物品i了
             dp[i][j] = dp[i-1][j]
          } else {
             dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
          }
       }
    }
    return dp[n-1][w] // 物品编号从0开始
}

1
2
3
4
5
6
7
8
9

func backpackMaxValue(n, w int, weight, value []int) int {
    dp := make([]int, w+1)
    for i := 0; i < n; i++ { // 物品
       for j := w; j >= weight[i]; j-- { // 背包容量，j从后往前遍历，同时为了让dp[j-weight[i]]的下标不小于0，j应该大于等于weight[i]
          dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
       }
    }
    return dp[w]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func canPartition(nums []int) bool {
    sum, maxVal, target := 0, 0, 0
    for i := 0; i < len(nums); i++ {
       sum += nums[i]
       if nums[i] > maxVal {
          maxVal = nums[i]
       }
    }
    target = sum / 2
    // 剪枝策略：数组中的最大值大于了sum/2 或者 sum为奇数，也直接返回false
    if maxVal > target || sum%2 != 0 {
       return false
    }
    dp := make([]int, target+1)      // dp[i]表示容量为i的背包的最大价值
    for i := 0; i < len(nums); i++ { // 物品
       for j := target; j >= nums[i]; j-- { // 背包容量
          dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
       }
    }
    return dp[target] == target
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func lastStoneWeightII(stones []int) int {
    sum, target := 0, 0
    for i := 0; i < len(stones); i++ {
       sum += stones[i]
    }
    target = sum / 2
    dp := make([]int, target+1)
    for i := 0; i < len(stones); i++ { // 先遍历物品
       for j := target; j >= stones[i]; j-- { // 再遍历背包容量，从大到小遍历
          dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
       }
    }
    return sum - dp[target] - dp[target]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func findTargetSumWays(nums []int, target int) int {
    sumA, sum := 0, 0
    for i := 0; i < len(nums); i++ {
       sum += nums[i]
    }
    if (target+sum)%2 != 0 { // 如果target+sum为奇数，则无法让表达式的和为target
       return 0
    }
    if target+sum < 0 { // 如果target为负数，且target小于了-sum，也无法让表达式的和为target
       return 0
    }
    sumA = (target + sum) / 2
    // 现在需要计算装满容量为sumA的背包有多少种方法
    dp := make([]int, sumA+1) // dp[j]表示装满容量为i的背包有dp[j]种方法
    dp[0] = 1
    for i := 0; i < len(nums); i++ { // 先遍历物品
       for j := sumA; j >= nums[i]; j-- { // 再遍历背包
          dp[j] += dp[j-nums[i]]
       }
    }
    return dp[sumA]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func findMaxForm(strs []string, m int, n int) int {
    dp := make([][]int, m+1)
    for i := 0; i <= m; i++ {
       dp[i] = make([]int, n+1)
    }
    for _, str := range strs { // 先遍历物品
       x, y := 0, 0                    // 遍历每个物品时，x和y重置
       for i := 0; i < len(str); i++ { // 计算添加的物品中0的个数和1的个数
          if str[i] == '0' {
             x++
          } else {
             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)
          }
       }
    }
    return dp[m][n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func change(amount int, coins []int) int {
    dp := make([]int, amount+1)
    dp[0] = 1
    for i := 0; i < len(coins); i++ { // 先遍历物品
       for j := coins[i]; j <= amount; j++ { // 再遍历背包容量（每个物品可以使用无限次，所以这里从小到大遍历）
          dp[j] += dp[j-coins[i]]
       }
    }
    return dp[amount]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func combinationSum4(nums []int, target int) int {
    dp := make([]int, target+1)
    dp[0] = 1
    // 对于排列问题，我们只需要交换两个循环的遍历顺序，先遍历背包容量，在遍历物品
    for j := 0; j <= target; j++ { // 先遍历背包容量（每个物品可以使用无限次，所以这里从小到大遍历）
       for i := 0; i < len(nums); i++ { // 再遍历物品
          if j-nums[i] >= 0 {
             dp[j] += dp[j-nums[i]]
          }
       }
    }
    return dp[target]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func main() {
    coins := []int{1, 2, 5}
    amount := 11
    r := coinChange(coins, amount)
    fmt.Println(r) // 3
}
func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    //minVal := 0
    for i := 0; i <= amount; i++ {
       if i == 0 {
          dp[i] = 0
       } else {
          dp[i] = math.MaxInt
       }
    }
    // 由于本题的dp数组值与物品的排列组合没有关系，所以先遍历物品或先遍历背包容量都可以
    for i := 0; i < len(coins); i++ { // 先遍历物品
       for j := coins[i]; j <= amount; j++ { // 完全背包问题，从小到大遍历
          if dp[j-coins[i]] != math.MaxInt { // dp[j-coins[i]]是初始时的最大值，则不需要更新dp[j]
             dp[j] = min(dp[j], dp[j-coins[i]]+1)
          }
       }
    }
    if dp[amount] == math.MaxInt {
       return -1
    }
    return dp[amount]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func numSquares(n int) int {
    nums := make([]int, 0) // 存放候选的平方数
    for i := 1; i*i <= n; i++ {
       nums = append(nums, i*i)
    }
    if nums[len(nums)-1] == n { // n本身就是完全平方数
       return 1
    }
    dp := make([]int, n+1)
    dp[0] = 0
    for i := 1; i <= n; i++ {
       dp[i] = math.MaxInt
    }
    for i := 0; i < len(nums); i++ {
       for j := nums[i]; j <= n; j++ {
          dp[j] = min(dp[j], dp[j-nums[i]]+1)
       }
    }
    return dp[n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func numSquares(n int) int {
	dp := make([]int, n+1)
	dp[0] = 0
	for i := 1; i <= n; i++ {
		dp[i] = math.MaxInt
	}
    // 遍历背包容量 和 遍历物品 的顺序可以交换
	for i := 1; i <= n; i++ { // 先遍历背包容量
		for j := 1; j*j <= i; j++ { // 再遍历物品
			dp[i] = min(dp[i], dp[i-j*j]+1)
		}
	}
	return dp[n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func numSquares(n int) int {
	dp := make([]int, n+1)
	dp[0] = 0
	for i := 1; i <= n; i++ {
		dp[i] = math.MaxInt
	}
	for i := 1; i*i <= n; i++ { // 先遍历物品
		for j := i * i; j <= n; j++ { // 再遍历背包容量
			dp[j] = min(dp[j], dp[j-i*i]+1)
		}
	}
	return dp[n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func wordBreak(s string, wordDict []string) bool {
    n := len(s)
    dp := make([]bool, n+1)
    dp[0] = true
    dict := make(map[string]bool, len(wordDict))
    for i := 0; i < len(wordDict); i++ {
       dict[wordDict[i]] = true
    }
    for j := 1; j <= n; j++ { // 先遍历背包容量
       for i := 0; i < j; i++ { // 再遍历物品
          if dp[i] && dict[s[i:j]] { // 判断某个位置能否对s进行切割，使切割后的子字符串在dict中，如果找到了，直接返回true，并结束本物品的循环
             dp[j] = true
             break
          }
       }
    }
    return dp[n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func rob(nums []int) int {
    if len(nums) == 1 {
       return nums[0]
    }
    n := len(nums)
    dp := make([]int, n)
    dp[0], dp[1] = nums[0], max(nums[0], nums[1])
    for i := 2; i < n; i++ { // 从位置2开始
       dp[i] = max(dp[i-1], dp[i-2]+nums[i])
    }
    return dp[n-1]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func main() {
    nums := []int{2, 3, 2}
    r := rob2(nums)
    fmt.Println(r) // 3
}
func rob2(nums []int) int {
    if len(nums) == 1 {
       return nums[0]
    }
    rob1 := func(nums []int) int {
       if len(nums) == 1 {
          return nums[0]
       }
       n := len(nums)
       dp := make([]int, n)
       dp[0], dp[1] = nums[0], max(nums[0], nums[1])
       for i := 2; i < n; i++ { // 从位置2开始
          dp[i] = max(dp[i-1], dp[i-2]+nums[i])
       }
       return dp[n-1]
    }
    return max(rob1(nums[1:]), rob1(nums[:len(nums)-1]))
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func rob3(root *TreeNode) int {
    var traversal func(root *TreeNode) [2]int // 返回值的第0个元素表示不选择该结点能获得的最大金额，第1个元素表示选择该结点能获得的最大金额
    traversal = func(root *TreeNode) [2]int {
       if root == nil { // 如果root为空，则选不选择root的最大金额都是0
          return [2]int{0, 0}
       }
       leftMaxVal := traversal(root.Left)
       rightMaxVal := traversal(root.Right)
       // 采用后序遍历
       val1 := root.Val + leftMaxVal[0] + rightMaxVal[0]                               // 选择root结点，则左右孩子结点就不能选择了
       val2 := max(leftMaxVal[0], leftMaxVal[1]) + max(rightMaxVal[0], rightMaxVal[1]) // 不选择root结点，则要选择root的左右孩子，但还需要去左、右孩子各自的最大金额，然后相加
       return [2]int{val2, val1}                                                       // 不选择在前面
    }
    return max(traversal(root)[0], traversal(root)[1]) // 返回 不选择 和 选择 root的情况中更大的值
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func maxProfit(prices []int) int {
    minPrice := prices[0]
    maxProfitVal := 0
    for i := 1; i < len(prices); i++ {
       if prices[i] < minPrice { // 更新最小值
          minPrice = prices[i]
       }
       if prices[i]-minPrice > maxProfitVal { // 更新最大利润
          maxProfitVal = prices[i] - minPrice
       }
    }
    return maxProfitVal
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func maxProfit(prices []int) int {
    n := len(prices)
    dp := make([][2]int, n)
    dp[0][0], dp[0][1] = -prices[0], 0
    for i := 1; i < n; i++ {
       dp[i][0] = max(dp[i-1][0], -prices[i])
       dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
    }
    return max(dp[n-1][0], dp[n-1][1]) // 取第n-1天持有和不持有的较大值
}

1
2
3
4
5
6
7
8
9

func maxProfit2(prices []int) int {
	sum := 0
	for i := 1; i < len(prices); i++ {
		if prices[i] > prices[i-1] {
			sum += prices[i] - prices[i-1]
		}
	}
	return sum
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func maxProfit2(prices []int) int {
    n := len(prices)
    dp := make([][2]int, n)
    dp[0][0], dp[0][1] = -prices[0], 0
    for i := 1; i < n; i++ {
       dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
       dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
    }
    return max(dp[n-1][0], dp[n-1][1]) // 取第n-1天持有和不持有的较大值
}