算法-生活中的动态规划及实现

package main import ( fmt ) // // 动态规划常见题型 Go 实现合集 // // 通用思路 // 1. 定义状态 dp[...] 表示什么 // 2. 找状态转移方程 // 3. 确定初始化 // 4. 确定遍历顺序 // 5. 返回最终答案 // // ------------------------------------------------------------ // 1. 爬楼梯 Climbing Stairs // // 题目每次可以走 1 阶或 2 阶走到第 n 阶有多少种方法 // // 状态dp[i] 到达第 i 阶的方法数 // 转移dp[i] dp[i-1] dp[i-2] // 初始化dp[1] 1, dp[2] 2 // 时间复杂度O(n) // 空间复杂度O(n) // ------------------------------------------------------------ func climbStairs(n int) int { if n 2 { return n } dp : make([]int, n1) dp[1] 1 dp[2] 2 for i : 3; i n; i { dp[i] dp[i-1] dp[i-2] } return dp[n] } // 爬楼梯空间优化版 // 因为 dp[i] 只依赖 dp[i-1] 和 dp[i-2] // 所以不需要保存整个数组。 // 空间复杂度O(1) func climbStairsOptimized(n int) int { if n 2 { return n } a, b : 1, 2 for i : 3; i n; i { a, b b, ab } return b } // ------------------------------------------------------------ // 2. 打家劫舍 House Robber // // 题目相邻房屋不能同时偷求最大收益。 // // 状态dp[i] 偷到第 i 间房时前 i1 间房的最大收益 // // 当前房屋有两种选择 // 1. 不偷dp[i-1] // 2. 偷dp[i-2] nums[i] // // 转移dp[i] max(dp[i-1], dp[i-2] nums[i]) // // 时间复杂度O(n) // 空间复杂度O(n) // ------------------------------------------------------------ func rob(nums []int) int { n : len(nums) if n 0 { return 0 } if n 1 { return nums[0] } dp : make([]int, n) dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i : 2; i n; i { dp[i] max( dp[i-1], // 不偷当前房屋 dp[i-2]nums[i], // 偷当前房屋 ) } return dp[n-1] } // 打家劫舍空间优化版 func robOptimized(nums []int) int { prev2 : 0 prev1 : 0 for _, money : range nums { current : max( prev1, // 不偷 prev2money, // 偷 ) prev2 prev1 prev1 current } return prev1 } // ------------------------------------------------------------ // 3. 不同路径 Unique Paths // // 题目机器人从左上角走到右下角只能向右或向下 // 一共有多少条路径 // // 状态dp[i][j] 到达位置 (i,j) 的路径数量 // // 当前位置只能来自 // 1. 上方 (i-1,j) // 2. 左方 (i,j-1) // // 转移dp[i][j] dp[i-1][j] dp[i][j-1] // // 时间复杂度O(m*n) // 空间复杂度O(m*n) // ------------------------------------------------------------ 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 } // 第一行只有一种走法一直向右 for j : 0; j n; j { dp[0][j] 1 } for i : 1; i m; i { for j : 1; j n; j { dp[i][j] dp[i-1][j] dp[i][j-1] } } return dp[m-1][n-1] } // ------------------------------------------------------------ // 4. 0/1 背包 // // 题目每个物品只能选一次。 // weights[i] 为重量values[i] 为价值capacity 为背包容量。 // // 状态dp[c] 容量为 c 时可获得的最大价值 // // 对于一个重量 w、价值 v 的物品 // dp[c] max(dp[c], dp[c-w] v) // // 关键容量必须从大到小遍历。 // 原因防止一个物品被重复使用。 // // 时间复杂度O(n*capacity) // 空间复杂度O(capacity) // ------------------------------------------------------------ func zeroOneKnapsack(weights []int, values []int, capacity int) int { dp : make([]int, capacity1) for i : 0; i len(weights); i { w : weights[i] v : values[i] // 0/1 背包必须倒序 for c : capacity; c w; c-- { dp[c] max( dp[c], dp[c-w]v, ) } } return dp[capacity] } // ------------------------------------------------------------ // 5. 零钱兑换 Coin Change // // 题目给定若干硬币面值每种硬币可以无限使用。 // 求凑出 amount 的最少硬币数。 // // 状态dp[x] 凑出金额 x 所需要的最少硬币数 // // 如果最后使用一枚 coin // dp[x] min(dp[x], dp[x-coin] 1) // // 初始化 // dp[0] 0 // 其他值初始化为一个很大的数 // // 时间复杂度O(amount * len(coins)) // 空间复杂度O(amount) // ------------------------------------------------------------ func coinChange(coins []int, amount int) int { const INF int(^uint(0)1) / 2 dp : make([]int, amount1) for i : 1; i amount; i { dp[i] INF } dp[0] 0 for x : 1; x amount; x { for _, coin : range coins { if x coin dp[x-coin] ! INF { dp[x] min( dp[x], dp[x-coin]1, ) } } } if dp[amount] INF { return -1 } return dp[amount] } // ------------------------------------------------------------ // 6. 最长递增子序列 LIS // // 题目求数组中的最长严格递增子序列长度。 // // 例如 // nums [10,9,2,5,3,7,101,18] // 答案 4 // 例如子序列 [2,3,7,101] // // 状态dp[i] 以 nums[i] 结尾的最长递增子序列长度 // // 如果 j i 且 nums[j] nums[i] // 那么 nums[i] 可以接在 nums[j] 后面 // // dp[i] max(dp[i], dp[j] 1) // // 时间复杂度O(n^2) // 空间复杂度O(n) // ------------------------------------------------------------ func lengthOfLIS(nums []int) int { if len(nums) 0 { return 0 } n : len(nums) dp : make([]int, n) answer : 1 for i : 0; i n; i { dp[i] 1 for j : 0; j i; j { if nums[j] nums[i] { dp[i] max( dp[i], dp[j]1, ) } } answer max(answer, dp[i]) } return answer } // ------------------------------------------------------------ // 7. 最长公共子序列 LCS // // 题目求两个字符串的最长公共子序列长度。 // // 状态 // dp[i][j] text1 前 i 个字符与 text2 前 j 个字符 // 的最长公共子序列长度。 // // 如果当前字符相同 // dp[i][j] dp[i-1][j-1] 1 // // 如果当前字符不同 // dp[i][j] max(dp[i-1][j], dp[i][j-1]) // // 时间复杂度O(m*n) // 空间复杂度O(m*n) // ------------------------------------------------------------ func longestCommonSubsequence(text1 string, text2 string) int { m : len(text1) n : len(text2) dp : make([][]int, m1) for i : 0; i m; i { dp[i] make([]int, n1) } for i : 1; i m; i { for j : 1; j n; j { if text1[i-1] text2[j-1] { dp[i][j] dp[i-1][j-1] 1 } else { dp[i][j] max( dp[i-1][j], dp[i][j-1], ) } } } return dp[m][n] } // ------------------------------------------------------------ // 工具函数 // ------------------------------------------------------------ func max(a int, b int) int { if a b { return a } return b } func min(a int, b int) int { if a b { return a } return b } // ------------------------------------------------------------ // 示例运行 // ------------------------------------------------------------ func main() { fmt.Println( 动态规划 Go 示例 ) // 1. 爬楼梯 fmt.Println(\n1. 爬楼梯) fmt.Println(n 5) fmt.Println(答案:, climbStairs(5)) fmt.Println(空间优化答案:, climbStairsOptimized(5)) // 2. 打家劫舍 fmt.Println(\n2. 打家劫舍) houses : []int{2, 7, 9, 3, 1} fmt.Println(房屋金额:, houses) fmt.Println(最大收益:, rob(houses)) fmt.Println(空间优化答案:, robOptimized(houses)) // 3. 不同路径 fmt.Println(\n3. 不同路径) fmt.Println(3 x 3 网格) fmt.Println(路径数量:, uniquePaths(3, 3)) // 4. 0/1 背包 fmt.Println(\n4. 0/1 背包) weights : []int{1, 3, 4} values : []int{15, 20, 30} capacity : 4 fmt.Println(weights:, weights) fmt.Println(values :, values) fmt.Println(capacity:, capacity) fmt.Println(最大价值:, zeroOneKnapsack(weights, values, capacity)) // 5. 零钱兑换 fmt.Println(\n5. 零钱兑换) coins : []int{1, 2, 5} amount : 11 fmt.Println(coins:, coins) fmt.Println(amount:, amount) fmt.Println(最少硬币数:, coinChange(coins, amount)) // 6. LIS fmt.Println(\n6. 最长递增子序列 LIS) nums : []int{10, 9, 2, 5, 3, 7, 101, 18} fmt.Println(nums:, nums) fmt.Println(LIS 长度:, lengthOfLIS(nums)) // 7. LCS fmt.Println(\n7. 最长公共子序列 LCS) text1 : abcde text2 : ace fmt.Println(text1:, text1) fmt.Println(text2:, text2) fmt.Println(LCS 长度:, longestCommonSubsequence(text1, text2)) }