算法-生活中的动态规划及实现
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)) }

相关新闻

Python基础语法练习题(51-52)

Python基础语法练习题(51-52)

今天接着来记录两个基础语法练习题。第五十一题,时间处理:#编写一个程序,使用time模块来实现时间处理功能#导入time模块,用于处理时间相关的任务import time#获取当前时间的时间戳,即自1970-01-01 00:00:00以来的秒数c…

2026/11/3 10:07:50 阅读更多 →
我把印象笔记的「加密导出」掰开揉碎,最后用一招绕过了它——本地明文库直提全攻略

我把印象笔记的「加密导出」掰开揉碎,最后用一招绕过了它——本地明文库直提全攻略

我把印象笔记的「加密导出」掰开揉碎,最后用一招绕过了它——本地明文库直提全攻略一次真实的自救:7 个 .notes 文件、7.7GB、正文全是密文。本文记录从逆向加密格式到最终 601 条笔记无损导出的全过程,包括每一步的踩坑、调试和验证方法。脚…

2026/10/19 16:40:26 阅读更多 →
在Word中快速实现同类内容应用“双行合一”格式

在Word中快速实现同类内容应用“双行合一”格式

最近在将金瓶梅词话HTML版改编成带目录与页眉且支持交叉链接的Word文档过程中&#xff0c;想将其中的批注处理成双行合一格式。书中共有三种批注&#xff1a;眉批、侧批、夹批。HTML代码分别是下面这几种形式&#xff1a;眉批&#xff1a;<span class"comment top-comm…

2026/10/28 2:57:31 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年&#xff0c;我大部分时间都在跟浏览器标签页打交道&#xff0c;直到第一次把桌面应用跑起来&#xff0c;才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词&#xff0c;最开始是在某段时间频繁出现在同事的讨论里&#xff0c;一个用HTML…

2026/11/16 8:22:12 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档&#xff0c;主要面向智能锁安装人员、终端用户及售后维护者&#xff0c;帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件&#xff0c;大小4.37MB&#xff0c;内容结构清晰&#xff…

2026/11/16 6:41:34 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统&#xff0c;整车要求空载跑到8m/s&#xff0c;电机转速已经拉到额定点&#xff0c;驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令&#xff0c;转速纹丝不动&#xff0c;三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/16 8:22:12 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年&#xff0c;用它写过嵌入式驱动、做过游戏服务端&#xff0c;也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词&#xff0c;我其实挺感慨的——这门语言的难点从来不是语法多&#xff0c;而是知识点之间的耦合太深…

2026/11/16 8:22:12 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书以PDF格式发布&#xff0c;适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开&#xff0c;先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能&#xff0c;再给出完整安装步骤&…

2026/11/16 7:30:18 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历&#xff1a;翻开源码注释、论文摘要或者一份专业报告&#xff0c;每个字都认识&#xff0c;连在一起却像天书。想找人聊聊&#xff0c;身边要么没人懂&#xff0c;要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型&#xff0c;几秒钟之后&a…

2026/11/16 8:22:12 阅读更多 →

日新闻

周新闻

月新闻