- 博客(6)
- 收藏
- 关注
RSS订阅原创 最长公共子序列问题：从暴力递归到动态规划详解
text2[j-1]，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。如果当前字符相等，则公共子序列的长度加一，并递归地继续比较剩下的部分。• 如果 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。• 如果两个字符串的当前字符相等，则公共子序列的长度可以增加 1，递归地处理去掉这两个字符后的子问题。例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
2025-01-07 16:42:08
1988
原创 分解贴纸问题：从暴力递归到动态规划详解
暴力递归的思路是通过递归遍历所有可能的组合，每次选择一个贴纸，减去目标字符串中可以被该贴纸覆盖的字符，递归解决剩下的部分，直到目标字符串为空或无法拼接为止。通过存储已经计算过的子问题的结果，可以大大减少计算的次数。如果在递归过程中遇到已经计算过的子问题，就直接返回缓存中的结果，而不重新计算。我们可以从收集的贴纸中切割字母并重新排列它们，且每种贴纸的数量是无限的。这道题的关键是利用每个贴纸拼出目标字符串，而每个贴纸的数量是无限的，实际上是自顶向下的递归方法，它通过递归的方式计算每个子问题的解，
2025-01-03 17:31:43
734
原创 纸牌游戏：从暴力递归到动态规划详解
在这道题目中，给定一个整型数组 arr，代表数值不同的纸牌排成一条线，玩家A和玩家B依次从两端选择纸牌。玩家A先拿，玩家B后拿，但每个玩家每次只能从最左或最右的纸牌中选择。玩家A和B都是绝顶聪明的，他们会选择最优的策略。在这种情况下，玩家A和B的选择策略会相互影响，因此需要考虑博弈的策略。• 递归暴力法：通过递归模拟每一步的选择，简单直观，但效率较低，尤其是在输入数据较大的情况下。：最坏情况下，每一步递归都会递归出两种选择，最终递归树的深度为。玩家A和玩家B依次拿走每张纸牌规定玩家A先拿，
2025-01-03 13:46:52
887
原创 机器人行进问题：从暴力递归到动态规划详解
我们可以定义一个二维数组dp[i][j]，表示在经过i步后，机器人处于位置j的方法数。最终的结果就是dp[K][P]，即经过KKK步到达位置PPP的方法数。
2025-01-03 10:02:45
1734
原创 数字字符串转化问题：从暴力递归到动态规划详解
给定一个仅包含数字字符的字符串，我们需要计算这个字符串能够被转化为多少种字母组合。那么一个数字字符串比如"111”就可以转化为:"AAA”、"KA"和“AK”动态规划解法的思想是通过状态转移来计算每个位置的转换方式数。给定一个只有数字字符组成的字符串str，返回有多少种转化结果。规定1和A对应、2和B对应、3和C对应…因此，任务是计算所有可能的转换结果的数量。个字符能够转化的不同的方式数。
2025-01-02 14:57:56
802
原创 0/1背包问题：从暴力递归到动态规划详解
题目：有一组数量为 n 个物品，每个物品都有重量w 和价值v给定一个背包bag，背包装的物品不能超过背包最大载重容量返回背包bag 能装下的最大价值1. 物品的重量和价值：2. 背包的容量：暴力解法的核心是递归，通过逐一决策每个物品是否放入背包，最终找到最优解。状态定义：递归逻辑：递归终止条件：动态规划解法递归的暴力解法有重复子问题，导致了大量的重复计算。为了解决这个问题，我们可以使用动态规划来优化。状态定义：状态转移：边界条件： 测试方法示例解析假设：我们希望找到在容量为
2024-12-31 15:32:36
1848
Downie 4 For Mac V4.5.11
2024-04-08
TouchbarPet Mac V0.8.2
2024-04-08
右键助手专业版 For Mac
2024-04-08
LyricsX V1.6.4
2024-04-08
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人