28-附：动态规划专题汇总.md

```Go
package main

import "math"

// 1-1、🎒背包问题：给定两个长度都为N的数组weights和values，weight[i]和values[i]分别代表i号物品的重量和价值。
// 给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少？
// w   重量数组
// v   价值数组
// bag 背包的最大容量
// 返回该背包所能装下的最大价值
func getMaxValue(w []int, v []int, bag int) int {
	// 初始传入w,v。index位置开始，alreadyW表示在index位置的时候，重量已经到达了多少
	return processBag(w, v, 0, 0, bag)
}

// 递归的第一种尝试
// 0..index-1上做了货物的选择，使得你已经达到的重量是多少 alreadyW
// 如果返回-1，认为没有方案
// 如果不返回-1，认为返回的值是真实价值
func processBag(w []int, v []int, index int, alreadyW int, bag int) int {
	// base case
	if alreadyW > bag {
		return -1
	}

	// 重量没超
	if index == len(w) {
		return 0
	}

	// 当前不选择index的货物情况下，后续的价值
	// 无需传递当前index的重量，且p1就是总价值
	p1 := processBag(w, v, index+1, alreadyW, bag)
	// 当前选择了index的货物，把重量加上，继续向下递归
	p2next := processBag(w, v, index+1, alreadyW+w[index], bag)
	// p2表示要了当前货物之后总价值应该是后续价值加上当前价值
	p2 := -1
	if p2next != -1 {
		p2 = v[index] + p2next
	}

	return int(math.Max(float64(p1), float64(p2)))
}

// 1-2、背包问题的第二种递归解法。
func maxValue(w []int, v []int, bag int) int {
	// 相比上一个暴力递归尝试，去掉了alreadyW。用背包剩余空间代替；rest表示背包剩余空间，初始剩余空间就是背包容量
	return processBag2(w, v, 0, bag)
}

func processBag2(w []int, v []int, index int, rest int) int {
	// base case 1 无效方案。背包剩余容量装不下当前重量的情况
	if rest < 0 {
		return -1
	}

	// rest >=0。index来到终止位置，没货物了，当前返回0价值
	// base case 2
	if index == len(w) {
		return 0
	}

	// 有货也有空间。当前index不选择，得到p1总价值
	p1 := processBag2(w, v, index+1, rest)
	p2 := -1
	// 选择了index位置，剩余空间减去当前重量
	p2Next := processBag2(w, v, index+1, rest-w[index])
	// 选择index的总价值，是index...的价值加上个当前index的价值
	if p2Next != -1 {
		p2 = v[index] + p2Next
	}

	return int(math.Max(float64(p1), float64(p2)))
}

// 1-3、0-1背包问题：动态规划解决方案。在递归的思路上改进
// 以背包问题举例，我们每一个重量有要和不要两个选择，且都要递归展开。那么我们的递归时间复杂度尾O(2^N)。
// 而记忆化搜索，根据可变参数得到的长为N价值为W的二维表，那么我们的时间复杂度为O(N*bag)。
// 如果递归过程中状态转移有化简继续优化的可能，例如枚举。那么经典动态规划可以继续优化，
// 否则记忆化搜索和动态规划的时间复杂度是一样的
func dpWay(w []int, v []int, bag int) int {
	N := len(w)
	// 准备一张dp表，行号为我们的重量范围bag+1。列为我们的价值数目个数的范围N+1。dp数组装下所有的可能性。
	dp := make([][]int, N+1)
	for i := 0; i < N+1; i++ {
		dp[i] = make([]int, bag+1)
	}

	// 由于暴力递归中index==w.length的时候，总是返回0。所以：
	// dp[N][...] = 0。整形数组初始化为0，无需处理
	// 由于N行已经初始化为0，我们从N-1开始。填我们的dp表
	for index := N - 1; index >= 0; index-- {
		// 剩余空间从0开始，一直填写到bag
		for rest := 0; rest <= bag; rest++ {
			// 通过正常位置的递归处理。我们转而填写我们的dp表
			// 所以我们p1等于dp表的下一层向上一层返回
			p1 := dp[index+1][rest]
			p2 := -1
			// rest - w[index] 不越界
			if rest-w[index] >= 0 {
				p2 = v[index] + dp[index+1][rest-w[index]]
			}
			// p1和p2取最大值
			dp[index][rest] = int(math.Max(float64(p1), float64(p2)))
		}
	}
	// 最终返回dp表的0，bag位置，就是我们暴力递归的主函数调用
	return dp[0][bag]
}

// 2、最长递增子序列问题
// 问题描述：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
// 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
// 例如：nums = [10,9,2,5,3,7,101,18]， 返回结果是4。最长递增子序列是 [2,3,7,101]，因此长度为 4 。
func lengthOfLIS(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	dp := make([]int, len(nums))

	dp[0] = 1
	// 全局最大
	max := 1

	for i := 1; i < len(nums); i++ {
		// 默认每个元素的dp[i]都为1，表示自己形成的递增子序列
		dp[i] = 1

		for j := 0; j < i; j++ {
			// 如果在当前位置的前面，存在一个比自己小的元素，该元素的dp[j]加上当前元素形成的新的dp[j] + 1比dp[i]大。更新这个dp[i]。否则不更新
			if nums[i] > nums[j] {
				dp[i] = int(math.Max(float64(dp[i]), float64(dp[j]+1)))
			}
		}

		// 最上层循环，每一轮检查是否需要更新全局max
		max = int(math.Max(float64(max), float64(dp[i])))
	}
	return max
}

// 3、最大连续子数组的和（最大子序和）
// 问题描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
// 例如：nums = [-2,1,-3,4,-1,2,1,-5,4]，返回6。连续子数组 [4,-1,2,1] 的和最大，为 6 。
func maxSubArray(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	N := len(nums)
	// dp[i] 含义：子数组必须以i结尾的时候，所有可以得到的子数组中，最大累加和是多少？
	dp := make([]int, N)
	dp[0] = nums[0]
	// 记录全局最大的子数组的和
	max := dp[0]
	for i := 1; i < N; i++ {
		// 当前的值
		p1 := nums[i]
		// 当前的值和上一个位置的最大和累加
		p2 := nums[i] + dp[i - 1]
		// dp[i]等于，当前的值，和当前值与上一个位置最大和的累加，取大的
		dp[i] = int(math.Max(float64(p1), float64(p2)))
		// 判断是否要更新全局最大值
		max = int(math.Max(float64(max), float64(dp[i])))
	}
	// 返回全局最大值
	return max
}

// 4、打家劫舍问题
// 问题描述：你是一个专业的小偷，计划偷窃沿街的房屋。
// 每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
// 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
// 示例输入：[1,2,3,1]， 输出4；偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
func rob(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	dp := make([]int, len(nums))

	for i := 0; i < len(nums); i++ {
		if i == 0 {
			dp[0] = nums[i]
		}
		if i == 1 {
			dp[1] = int(math.Max(float64(dp[0]), float64(nums[i])))
		}
		if i > 1 {
			dp[i] = int(math.Max(float64(dp[i - 1]), float64(dp[i - 2] + nums[i])))
		}
	}
	return dp[len(nums) - 1]
}

// 5、爬楼梯问题。
// 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
// 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
func climbStairs(n int) int {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	if n == 2 {
		return 2
	}

	dp := make([]int, n + 1)
	dp[1] = 1
	dp[2] = 2
	for i := 3; i <= n; i++ {
		dp[i] = dp[i - 1] + dp[i - 2]
	}
	return dp[n]
}

// 6、两个字符串的最长公共子序列问题
// 例如“ab1cd2ef345gh”和“opq123rs4tx5yz”的最长公共子序列为“12345”。即在两个字符串所有相等的子序列里最长的。所以返回子序列的长度5
func lcse(str1 []byte, str2 []byte) int {
	if len(str1) == 0 {
		return 0
	}
	if len(str2) == 0 {
		return 0
	}

	dp := make([][]int, len(str1))
	for i := 0; i < len(str1); i++ {
		dp[i] = make([]int, len(str2))
	}
	if str1[0] == str2[0] {
		dp[0][0] = 1
	} else {
		dp[0][0] = 0
	}

	// 填第0列的所有值
	// 一旦st1r的i位置某个字符等于str2的0位置，那么之后都是1
	for i := 1; i < len(str1); i++ {
		flag := -1
		if str1[i] == str2[0] {
			flag = 1
		} else {
			flag = 0
		}
		dp[i][0] = int(math.Max(float64(dp[i - 1][0]), float64(flag)))
	}

	// 填第0行的所有值
	// 一旦str2的j位置某个字符等于str1的0位置，那么之后都是1
	for j := 1; j < len(str2); j++ {
		flag := -1
		if str1[0] == str2[j] {
			flag = 1
		} else {
			flag = 0
		}
		dp[0][j] = int(math.Max(float64(dp[0][j - 1]), float64(flag)))
	}

	for i := 1; i < len(str1); i++ {
		for j := 1; j < len(str2); j++ {
			// dp[i - 1][j]表示可能性2
			// dp[i][j - 1] 表示可能性3
			dp[i][j] = int(math.Max(float64(dp[i - 1][j]), float64(dp[i][j - 1])))
			if str1[i] == str2[j] {
				dp[i][j] = int(math.Max(float64(dp[i][j]), float64(dp[i - 1][j - 1] + 1)))
			}
		}
	}
	return dp[len(str1) - 1][len(str2) - 1]
}
```