算法 - (动态规划)

2022-01-17 5636 words 12 minutes

Warning

本文最后更新于 July 31, 2022，文中内容可能已过时，请谨慎使用。

动态规划

讲解动态规划的资料很多，官方的定义是指把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。概念中的各阶段之间的关系，其实指的就是状态转移方程。很多人觉得DP难（下文统称动态规划为DP），根本原因是因为DP区别于一些固定形式的算法（比如DFS、二分法、KMP），没有实际的步骤规定第一步第二步来做什么，所以准确的说，DP其实是一种解决问题的思想。

动态规划的关键在于状态的定义，比如 opt[n] 、dp[n]、fib[n] 等。另外就是状态转移方程：opt[n] = best_of(opt[n-1], opt[n-2], …)

No.53 最大子序和

链接：https://leetcode.cn/problems/maximum-subarray/
思路：我们创建一个 DP 数组，用来存储每一位上包含第N位情况下的最大子序和，而每一位上包含第N位的最大和等于 max(dp[n-1], dp[n])

func maxSubArray(nums []int) int {
	var dp []int 
	dp = make([]int, len(nums))
	
	dp[0] = nums[0]
	for i := 1; i < len(nums) ; i++ {
		dp[i] = max(dp[i-1]+ nums[i], nums[i])		
	}
	
	max := -10000000000
	for _, v := range dp {
		if v > max {
			max = v 
		}
	}
	return max 
}

No.55 跳跃游戏

链接: https://leetcode.cn/problems/jump-game/
思路：

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

No.64 最小路径和

链接：https://leetcode.cn/problems/minimum-path-sum/
思路：一道标准的 dp 题，由于原题提示了每次只能向下或者向右移动一步，使得题目简单不少。我们假设一个二维数组，dp[i][j] ，和三角形最短路径一个思路。

func minPathSum(grid [][]int) int {
	if len(grid) == 0 {
		return 0
	}
	if len(grid) == 1 && len(grid[0]) == 1 {  // 1 x 1 正方形
		return grid[0][0]
	}

	var length, width int
	dp := make([][]int, len(grid))

	for i, _ := range grid {
		dp[i] = make([]int, len(grid[0]))
	}
	width = len(grid)
	length = len(grid[0])

	//fmt.Println(length, width)

	for i := 0; i < len(grid); i ++ {
		for j := 0; j < len(grid[i]); j ++ {
			if i == 0 && j == 0 {
				dp[0][0] = grid[0][0]
			} else if i == 0 {  // 第一层，没有上层
				dp[i][j] = grid[i][j] + dp[i][j-1]
			} else if j == 0 {  // 第一列，没有左边
				dp[i][j] = grid[i][j] + dp[i-1][j]
			} else {   			// 左边或者上边
				dp[i][j] = min(grid[i][j] + dp[i-1][j], grid[i][j] + dp[i][j-1])
			}
		}
	}

	return dp[width-1][length-1]
}

No.70 爬楼梯

链接：https://leetcode.cn/problems/climbing-stairs/
思路：假设我当前爬到第 N 层，那么我多少种爬法？爬到第N层无非最后一次爬是有两种可能，最后一次爬2楼，最后一次爬1楼，最后一次爬两楼的话，就变成了 dp[n] = dp[n-2] , 最后一次爬一楼就变成了 dp[n] = dp[n-1] ,组合起来就是 dp[n] = dp[n-1] + dp[n-2]

为了从1开始计算到n，每层楼梯有多少种爬法，还需要一次循环

func climbStairs(n int) int {
	if n == 1 {
		return 1
	}
	dp := make([]int, n+1)

	dp[1] = 1 // 一层楼梯1种爬法
	dp[2] = 2 // 两层楼梯2种爬法，一次爬2层，爬2个一层

	for i := 3; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}

	return dp[n]
}

No.72 编辑距离

链接: https://leetcode.cn/problems/edit-distance/
思路：使用动态规划解决编辑距离问题。dp[i][j]表示word1前i个字符转换为word2前j个字符的最少操作数。当字符相同时无需操作，不同时取插入、删除、替换三种操作的最小值。时间复杂度O(m×n)，空间复杂度O(m×n)。

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

func minDistance(word1 string, word2 string) int {
	m, n := len(word1), len(word2)
	
	// dp[i][j]表示word1前i个字符转换为word2前j个字符的最少操作数
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	
	// 初始化边界条件
	// word1前i个字符转换为空字符串，需要删除i次
	for i := 0; i <= m; i++ {
		dp[i][0] = i
	}
	// 空字符串转换为word2前j个字符，需要插入j次
	for j := 0; j <= n; j++ {
		dp[0][j] = j
	}
	
	// 填充DP表
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if word1[i-1] == word2[j-1] {
				// 字符相同，不需要操作
				dp[i][j] = dp[i-1][j-1]
			} else {
				// 字符不同，取三种操作的最小值
				dp[i][j] = min(
					dp[i-1][j]+1,   // 删除word1[i-1]
					dp[i][j-1]+1,   // 插入word2[j-1]
					dp[i-1][j-1]+1, // 替换word1[i-1]为word2[j-1]
				)
			}
		}
	}
	
	return dp[m][n]
}

func min(a, b, c int) int {
	if a <= b && a <= c {
		return a
	}
	if b <= c {
		return b
	}
	return c
}

No.118 杨辉三角

链接：https://leetcode.cn/problems/pascals-triangle/
思路：其实还是没觉得是一道标准的动态规划问题。就是2层循环，第一层设置好一个首尾值为1的数组。数组中间从上层数组中取值即可。

func generate(numRows int) [][]int {
	ans := make([][]int, numRows)
	for i := 0; i < numRows; i ++ {
		ans[i] = make([]int, i+1)
		ans[i][0] = 1
		ans[i][i] = 1
		for j := 1; j < i; j++ {
			ans[i][j] = ans[i-1][j] + ans[i-1][j-1]
		}
	}
	return ans
}

No.120 三角形最小路径和

链接：https://leetcode.cn/problems/triangle/
思路：假设如下三角型

随便选一个节点，如何判断到达此节点的最小路径呢。比如最后一行的数字 1 , dp[3][1] , 其最小值是从 dp[2][0] 和 dp[2][1] 里选一个。以此类推，一个标准的 dp。

func minimumTotal(triangle [][]int) int {
	if len(triangle) < 1 {
		return 0
	}
	if len(triangle) == 1 {
		return triangle[0][0]
	}
	dp := make([][]int, len(triangle))
	for i, arr := range triangle {
		dp[i] = make([]int, len(arr))
	}

	dp[0][0] = triangle[0][0]

	for i := 1 ; i < len(triangle); i ++ {
		for j := 0 ; j < len(triangle[i]); j ++ {
			if j == 0  {         // j 是三角左边只能选择侧边
				dp[i][j] = triangle[i][j] + dp[i-1][0]
			}else if j == len(triangle[i])-1 {  // j 是三角右边，只能选侧边
				dp[i][j] = triangle[i][j] + dp[i-1][j-1]
			}else {   // 三角中间，随便选
				dp[i][j] = min(triangle[i][j] + dp[i-1][j], triangle[i][j] + dp[i-1][j-1])
			}
		}
	}
	min := 1000000000000
	lastLevel := dp[len(triangle)-1]
	for _, v := range lastLevel {
		if v < min {
			min = v
		}
	}
	return min
}

No.121 买卖股票的最佳时机

链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
思路：因为要最大获利。所以就不是最大数减去最小数那么简单了。

比如：[7, 1, 5, 3, 6, 4] , 最大获利是 5

[1,2,3,4,5] 最大获利是4

[7,6,3,2] 最大获利就是0

这个题的思路就从历史最低点买入，存入历史最低值。用之后的数减去最低值。

其实并不是一道动态规划的做法。

func maxProfit(prices []int) int {
	var max int
	var minProfile int = 1000000
	n := len(prices)
	for i := 0 ; i < n; i++ {
		if minProfile > prices[i] {
			minProfile = prices[i]
		}
		if prices[i] - minProfile > max {
			max = prices[i] - minProfile
		}
	}
	return max
}

No.139 单词拆分

链接：https://leetcode.cn/problems/word-break/
思路：
- 方法1：动态规划（经典解法）
  - dp[i]表示s[0:i]是否可以被拆分
  - 状态转移：dp[i] = dp[j] && wordSet[s[j:i]]
  - 时间复杂度O(n²)，空间复杂度O(n)
- 方法2：BFS
  - 将问题看作图搜索，从位置0开始找到位置n的路径
  - 使用visited数组避免重复访问
  - 时间复杂度O(n²)，空间复杂度O(n)

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

// 方法1：动态规划
func wordBreak(s string, wordDict []string) bool {
	n := len(s)
	// dp[i]表示s[0:i]是否可以被拆分
	dp := make([]bool, n+1)
	dp[0] = true // 空字符串可以被拆分
	
	// 将wordDict转换为map提高查找效率
	wordSet := make(map[string]bool)
	for _, word := range wordDict {
		wordSet[word] = true
	}
	
	for i := 1; i <= n; i++ {
		for j := 0; j < i; j++ {
			// 如果s[0:j]可以拆分，且s[j:i]在字典中
			if dp[j] && wordSet[s[j:i]] {
				dp[i] = true
				break
			}
		}
	}
	
	return dp[n]
}

// 方法2：BFS
func wordBreakBFS(s string, wordDict []string) bool {
	wordSet := make(map[string]bool)
	for _, word := range wordDict {
		wordSet[word] = true
	}
	
	queue := []int{0}
	visited := make([]bool, len(s)+1)
	visited[0] = true
	
	for len(queue) > 0 {
		start := queue[0]
		queue = queue[1:]
		
		for end := start + 1; end <= len(s); end++ {
			if visited[end] {
				continue
			}
			
			word := s[start:end]
			if wordSet[word] {
				if end == len(s) {
					return true
				}
				visited[end] = true
				queue = append(queue, end)
			}
		}
	}
	
	return false
}

No.152 乘积最大子数组

链接：https://leetcode.cn/problems/maximum-product-subarray/
思路：做过No 53 的和最大子数组就会很容易理解这道题，只需要同时考虑负负得正就可以

func max3(a,b,c int) int {
	if a >= b && a >= c {
		return a 
	}
	if b >= c && b >= a {
		return b 
	}
	return c 
}

func min3(a,b,c int) int {
	if a <= b && a <= c {
		return a 
	}
	if b <= a && b <= c {
		return b 
	}
	return c 
}

func maxProduct(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	
	dp1 := make(map[int]int)
	dp2 := make(map[int]int)
	dp1[0] = nums[0]   // 存最大
	dp2[0] = nums[0]   // 存最小，一个负数 * 一个负数可能最大
	max := dp1[0]
	for i := 1; i < len(nums); i ++ {
		dp1[i] = max3(nums[i], nums[i]*dp1[i-1], nums[i]*dp2[i-1])
		dp2[i] = min3(nums[i], nums[i]*dp1[i-1], nums[i]*dp2[i-1])
		if dp1[i] > max {
			max = dp1[i]
		}
	}
	return max 
}

No.198 打家劫舍

链接：https://leetcode.cn/problems/house-robber/
思路：和最大子序和是一个思路，只不过这里多了一个逻辑就是不允许选择相邻的两个数。假设我选择打劫第N家，为达利益最大化，可以对比打劫第N家、 dp[N-2] 之和还是从第N-1 家重新开始打劫。

func rob(nums []int) int {
    if len(nums) == 0 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}

	dp := make([]int, len(nums))
	m := 0
	dp[0] = nums[0]
	dp[1] = max(nums[0], nums[1])
	for i := 2; i < len(nums) ; i++ {
		dp[i] = max(dp[i-2]+nums[i], dp[i-1]) // 上上家和本家还是上家
	}
	for _, v := range dp {
		if m < v {
			m = v 
		}
	}

	return m
}

No.221 最大正方形

链接: https://leetcode.cn/problems/maximal-square/
思路：动态规划

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

// 寻找只包含'1'的最大正方形，返回其面积
func maximalSquare(matrix [][]byte) int {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return 0
	}

	rows, cols := len(matrix), len(matrix[0])
	maxSide := 0
	
	// 创建dp数组，dp[i][j]表示以(i,j)为右下角的最大正方形边长
	dp := make([][]int, rows)
	for i := range dp {
		dp[i] = make([]int, cols)
	}

	// 初始化第一列
	for i := 0; i < rows; i++ {
		if matrix[i][0] == '1' {
			dp[i][0] = 1
			maxSide = 1
		}
	}

	// 初始化第一行
	for j := 0; j < cols; j++ {
		if matrix[0][j] == '1' {
			dp[0][j] = 1
			maxSide = 1
		}
	}

	// 填充dp表
	for i := 1; i < rows; i++ {
		for j := 1; j < cols; j++ {
			if matrix[i][j] == '1' {
				// 状态转移方程：当前位置的最大正方形边长 = 左上角、上方、左方三个位置的最小值 + 1
				dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1
				if dp[i][j] > maxSide {
					maxSide = dp[i][j]
				}
			} else {
				dp[i][j] = 0
			}
		}
	}

	// 返回面积（边长的平方）
	return maxSide * maxSide
}

No. 279 完全平方数

链接：https://leetcode.cn/problems/perfect-squares/
思路：方法1：动态规划
- dp[i]表示和为i的完全平方数最少数量
- 状态转移：dp[i] = min(dp[i], dp[i-j²]+1)
- 时间复杂度O(n√n)，空间复杂度O(n)

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

func numSquares(n int) int {
	// dp[i]表示和为i的完全平方数的最少数量
	dp := make([]int, n+1)
	
	// 初始化：除了0以外，都设为最大值
	for i := 1; i <= n; i++ {
		dp[i] = i // 最坏情况：全部用1来组成
	}
	
	// 遍历每个数
	for i := 1; i <= n; i++ {
		// 尝试所有可能的完全平方数
		for j := 1; j*j <= i; j++ {
			square := j * j
			dp[i] = min(dp[i], dp[i-square]+1)
		}
	}
	
	return dp[n]
}

No.300 最长递增子序列

链接：https://leetcode.cn/problems/longest-increasing-subsequence/
思路：动态规划，下标为i的值加入之后，最长值是多少

func lengthOfLIS(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	maxV := 1
	// 使用切片来实现 dp 数组
	dp := make([]int, len(nums))
	// 初始化 dp 数组，每个元素初始值为 1
	for i := range dp {
		dp[i] = 1
	}

	for i := 1; i < len(nums); i++ {
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		maxV = max(maxV, dp[i])
	}

	return maxV
}

No.322 零钱兑换

链接：https://leetcode.cn/problems/coin-change/
思路：这道题是一个典型的背包问题。这个问题可以拆开来看，还是dp思路，假设我 amount 是10, 那么我可以凑一个1元、2元或者5元时。
- 差1元的话，那么看9元怎么凑，而9元又需要差1、2、5 这么个凑法。
- 差2元的话，那么看8元怎么凑，而8元又需要差1、2、5 这么个凑发。
- 以此类推

func coinChange(coins []int, amount int) int {
	dp := make([]int, amount+1)

	// 初始化dp[0]
	dp[0] = 0

	for i := 1; i <= amount; i++ {  // 总金额逐渐递增
		dp[i] = math.MaxInt32
		for j := 0; j < len(coins); j ++ {
			if i >= coins[j] {   // dp[i]会被更新len(coins)次、找到差最少的
				dp[i] = min(dp[i], dp[i-coins[j]] + 1)   
			}
		}
	}

	// 没找到刚好 == 总额的
	if dp[amount] == math.MaxInt32 {
		return -1
	}
	return dp[amount]
}

No.392 判断子序列

链接：https://leetcode.cn/problems/is-subsequence/
思路：设 dp[i][j] 表示 s 的前 i 个字符是否是 t 的前 j 个字符的子序列。这里 i 的范围是 0 到 len(s)，j 的范围是 0 到 len(t)。

func isSubsequence(s string, t string) bool {
    m, n := len(s), len(t)
    // 创建二维数组 dp 用于存储状态
    dp := make([][]bool, m+1)
    for i := range dp {
        dp[i] = make([]bool, n+1)
    }

    // 初始化：空字符串是任何字符串的子序列
    for j := 0; j <= n; j++ {
        dp[0][j] = true
    }

    // 动态规划填充 dp 数组
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s[i-1] == t[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = dp[i][j-1]
            }
        }
    }

    return dp[m][n]
}

第二种方法，

func isSubsequence(s string, t string) bool {
	index := 0
	var flag bool
	for i := 0 ; i < len(s); i++ {
		flag = false
		for k := index ; k < len(t) ; k++ { // 循环长字符串
			if t[k] == s[i] {
				index = k+1     // 记录已找到的部分，下次从这继续开始找
				flag = true
				if i+1 == len(s) {  // 短字符串已经遍历到头了
					return flag
				}
				break
			}
		}
		if flag == false {
			return flag
		}
	}
	return false
}

第三种方法，双指针法

func isSubsequence(s string, t string) bool {
    sPtr := 0
    tPtr := 0

    for tPtr < len(t) && sPtr < len(s) {
        if s[sPtr] == t[tPtr] {
            sPtr++
        }
        tPtr++
    }

    // 如果 sPtr 最终等于 s 的长度，说明 s 中的所有字符都按顺序在 t 中找到了。
    return sPtr == len(s)
}

No.509 斐波那契数

链接：https://leetcode.cn/problems/fibonacci-number/
思路：这道题本身不难，就是简单的公式 dp[n] = dp[n-1] + dp[n-2] ,但是我错了好几遍才提交成功，主要是一些边界情况忘记处理。

func fib(n int) int {
	if n == 0 {
		return 0
	}
	var dp []int
	dp = make([]int, n+1)
	dp[0] = 0
	dp[1] = 1
	for i := 2;i <= n; i ++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

No.647 回文子串

链接: https://leetcode.cn/problems/palindromic-substrings/
思路：这个 Go 语言实现使用动态规划来解决回文子串计数问题。

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。

func countSubstrings(s string) int {
	n := len(s)
	count := 0
	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, n)
	}

	for i := n - 1; i >= 0; i-- {
		for j := i; j < n; j++ {
			if s[i] == s[j] && (j-i <= 1 || dp[i+1][j-1]) {
				dp[i][j] = true
				count++
			}
		}
	}
	return count
}

No.746 使用最小花费爬楼梯

链接：https://leetcode.cn/problems/min-cost-climbing-stairs/
思路：这道题有点像闯关类游戏。我们假设所处第N层时，怎么到第N层消耗最少。这个就是对比，跨2层还是跨一层。跨2层的消耗是 cost(n-2) ，同理跨一层的消耗是 cost[n-1]。如果楼梯总数小于2的话，一步就可以迈到终点。

func minCostClimbingStairs(cost []int) int {
	n := len(cost)
    dp := make([]int, n+1)
    dp[0] = 0
    dp[1] = 0 
    for i := 2; i <= n; i++ {
        dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
    }
    return dp[n]
}

Contents

算法 - (动态规划)

动态规划

No.53 最大子序和

No.55 跳跃游戏

No.64 最小路径和

No.70 爬楼梯

No.72 编辑距离

No.118 杨辉三角

No.120 三角形最小路径和

No.121 买卖股票的最佳时机

No.139 单词拆分

No.152 乘积最大子数组

No.198 打家劫舍

No.221 最大正方形

No. 279 完全平方数

No.300 最长递增子序列

No.322 零钱兑换

No.392 判断子序列

No.509 斐波那契数

No.647 回文子串

No.746 使用最小花费爬楼梯