Kiosk's/
Posts Thematic Tags Categories Express About
Kiosk's/

Contents

算法 - (动态规划)

 included in Algorithm
   3318 words   7 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.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.746 使用最小花费爬楼梯

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

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]
}

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

比如：[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.152 乘积最大子数组

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.300 最长递增子序列

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.392 判断子序列

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
}

No.509 斐波那契数

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]
}

No53. 最大子序和

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.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.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 三角形最小路径和

   2
  3 4
 6 5 7
4 1 8 3

随便选一个节点，如何判断到达此节点的最小路径呢。比如最后一行的数字 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.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.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]
}

Updated on 2022-07-31
Read Markdown
Back | Home