A PATH THROUGH THE GARDEN
🔢动态规划算法.
这里收录了 7 篇与「🔢动态规划算法」有关的文字。
2645. 构造有效字符串的最少插入数🔖DP🔖穷举
题目：https://leetcode.cn/problems/minimum-additions-to-make-valid-string/动态规划DP问题，两个步骤：状态转移方程第一项作为边界情况，暂不考虑，从第二项往后看，三项之间的规律:当i-1项>i-2项：需要剪掉一个完整abc整体，
63. 不同路径 II🔖DP
https://leetcode.cn/problems/unique-paths-ii动态规划62. 不同路径🔖DP题目的延申。这个题目的难点不是在状态转移方程的建立，而是初始状态的建立。数据预处理说明，对障碍物或是走不通的格子都设置为0状态转移方程不变。和62. 不同路径🔖DP中的方程...
70. 爬楼梯🔖DP
https://leetcode.cn/problems/climbing-stairs/动态规划动态规划解题主要是解决两点：状态转移方程（定义子问题）初始状态状态转移方程到达第n层阶梯的方式只有两种，走一步然后结束，或者走两步然后结束。到达第n-1层阶梯的方式只有两种，走一步然后结束，或者走...
62. 不同路径🔖DP
https://leetcode-cn.com/problems/unique-paths/动态规划状态转移方程：动态方程抽离问题的共同解决方程在本问题中，走到某个格子，他的上一步一定是从左边格子走进来或是从上边走下来的，所以利用这一点可以写一个函数表达式fij = fi-1j...
莱文斯坦距离(LD)问题
问题描述Levenshtein Distance也称莱文斯坦距离具体形式就是求一个字符串到另一个字符串所需要的最少操作步数，操作形式有：替换字母删除字母插入字母问题分析利用动态规划思想，将其剖析为一个个子问题，用其子问题的解决方式来解决该问题。问题分解出来的子问题存在重叠的情况，这是区分分治算...
TSP问题
问题描述假设有n个城市，各个城市与城市间的距离也已知，有一位旅行商需要途径所有的这n个城市，且每个城市只能且必须经过以此，求出一条路线，使得旅行商所走过的路程最短问题思路代码思路代码实现参考资料旅行推销商问题TSP的动态规划解法TSP(旅行者问题)——动态规划详解
0-1背包问题
问题描述问题描述给定一组已知重量和价值的物品和一个容量已知的背包，求解在不超过背包容量情况下，选用那些物品放入背包，使得所选用的所有物品价值最大化。物品总数N4背包容量M8每个物品重量wi5, 4, 3, 2每个物品价值vi15, 10, 6, 2问题的判定性说法问题的形式化定义问题思...