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

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, 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] } // 爬楼梯空间优化版 // 因为 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, a+b } return b } // ------------------------------------------------------------ // 2. 打家劫舍 House Robber // // 题目：相邻房屋不能同时偷，求最大收益。 // // 状态：dp[i] = 偷到第 i 间房时，前 i+1 间房的最大收益 // // 当前房屋有两种选择： // 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, // 不偷 prev2+money, // 偷 ) 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, capacity+1) 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, amount+1) 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, m+1) for i := 0; i <= m; i++ { dp[i] = make([]int, n+1) } 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)) }