首页
个人开发
工作相关
搜索
登录
搜索
colo
欲买桂花同载酒
累计撰写
1823
篇文章
累计收到
0
条评论
首页
栏目
首页
个人开发
工作相关
动态规划
2025-12-12
零钱兑换的最少硬币数
使用动态规划解决零钱兑换问题：定义 dp[i] 表示组成金额 i 所需的最少硬币数初始化 dp[0] = 0，其他为极大值（如 amount+1）状态转移方程：dp[i] = min(dp[i], dp[i - coin] + 1)遍历所有金额（1 到 amount）和所有硬币面额最终结果：若 dp[amount] 未更新则返回 -1，否则返回 dp[amount]
2025年-12月-12日
4 阅读
0 评论
动态规划
2025-12-12
爬楼梯问题
使用动态规划解决爬楼梯问题：定义状态：dp[i] 表示爬到第 i 阶楼梯的方法数状态转移方程：dp[i] = dp[i-1] + dp[i-2]边界条件：dp[0] = 1, dp[1] = 1时间复杂度：O(n)，空间复杂度：O(n)（可优化为 O(1)）
2025年-12月-12日
4 阅读
0 评论
动态规划
2025-12-12
最长递增子序列的长度
给定一个整数数组，求最长严格递增子序列的长度。解决方案：定义 dp[i] 表示以 nums[i] 结尾的最长递增子序列长度初始化所有 dp[i] = 1（每个元素自身构成子序列）状态转移：dp[i] = max(dp[i], dp[j] + 1) 当 j < i 且 nums[j] < nums[i]最终结果为 max(dp)时间复杂度 O(n²)，空间复杂度 O(n)
2025年-12月-12日
4 阅读
0 评论
动态规划
2025-12-11
爬楼梯的最小成本
题目要求计算爬到楼梯顶部的最小成本，每次可以爬1或2阶台阶。状态定义：dp[i]表示到达第i阶的最小成本状态转移：dp[i] = cost[i] + min(dp[i-1], dp[i-2])初始状态：dp[0] = cost[0], dp[1] = cost[1]最终结果：min(dp[n-1], dp[n-2])空间优化：只需保存前两个状态，空间复杂度O(1)
2025年-12月-11日
5 阅读
0 评论
动态规划
