解决|关于动态规划，你想知道的都在这里了！( 四 ) 实例|于同|最短路径|子结构

下面是由下而上的解决方案。
边界条件定义在矩阵的边界上。只有一种方法可以获得边界上的点：从上一个点向右或向下移动一个格子。
大家可以在下方链接中试着编写并测试一下自己的解决方案。
（链接地址：https://leetcode.com/problems/minimum-path-sum/?ref=hackernoon.com）
（2）背包问题
给定两个整数数组val[0..n - 1]和wt [0 . .n-1]，分别表示与n个物品相关的值和权重。同时，给定一个代表背包容量的整数W，求val [ ]的最大值子集，保证这个子集的权重之和小于或等于W。背包里的物品都必须保持完整，要么选择完整的物品，要么不选（0 - 1属性）。
解决方案
试着想出一个递归解决方案。在此基础上，添加一个缓存层，我们就会得到一个自上而下的动态规划解决方案了！
意思是，对于每一样物品，我们都有两个选择：
我们可以把这样物品放到背包里（如果合适的话)，背包的总价值增加，容量减少。
我们可以放弃这样物品，背包里的价值和容量不变。
在试过所有组合之后，我们只选择最大值。这个过程极其缓慢，但却是迈向最终解决方案的第一步。
我们必须在两个选项之间做出决定（向集合中添加一个元素或跳过它），在许多问题中都面临这样的选择，所以我们一定要了解，并理解其应用场合和方式。
以下是由下而上的解决方案：
（3）最长公共子序列
给定两个字符串text 1和text 2，返回它们最长公共子序列的长度。
字符串的子序列是在不改变其余字符相对顺序的情况下，从原字符串中删除一些字符（也可以不删除）后生成的新字符串，例如，“ace”是“abcde”的子序列，但“aec”不是。两个字符串共同的子序列就被称为其公共子序列。
如果没有公共子序列的话，则返回0。
例子：
输入：text 1 = “abcde”, text 2 = “ace”
输出：3
说明：最长公共子序列是 “ace” ，且其长度为3
解决方案
同样，计算最长X的问题，动态规划应该可以帮得上忙。
鉴于大家已经有了一些动态规划的经验了，我就直接从示例中的两个属性说起。我们将字符串称为A和B，这个问题的解为f（A, B），解题思路是看最后两个字符是否相等：
如果相等，那么LCS的长度至少为1。我们需要调用f(A[0:n-1]， B[0:n-1])来查找该索引前的LCS，并加1，因为A[n]和B[n]是相同的。
如果不相等，我们就删除两个字符串的最后一个字符——一次删一个，并查找生成LCS的路径。换句话说，我们取f(A[0: n-1]， B)和f(A, B[0:n-1])的最大值。
重叠子问题：我们来看看可能会出现的调用：(“abcde”, “ace”)产生x1 = (“abcd”, “ace”)和y1 = (“abcde”, “ac”)；x1将产生x12 = (“abc”, “ace”) 和y12= (“abcd”, “ac”)；y1将产生(“abcd”, “ac”)和(“abcde”, “a”)。如你所见，同样的问题需要计算很多次。
最优子结构：与最长递增子序列非常类似。如果我们在其中一个字符串A’中添加一个额外的字符，就可以从所有的缓存结果中快速计算出解决方案，而这些结果是我们解A和B得到的。
虽然用例子来证明理论并不是开始数学证明的好方法，但是对于应付编程面试来说已经绰绰有余了。
大家可以在下方链接中试着编写并测试一下自己的解决方案。
（链接地址：https://leetcode.com/problems/longest-common-subsequence/?ref=hackernoon.com）
总结
我们一定要了解这些问题，因为很多其他问题都只是在此基础上的变种而已，但是不要死记硬背。主动去了解动态规划的使用场景和应用方式，并坚持练习，直到可以轻松地将自己的想法转换成代码。如你所见，这是需要讲究方法的。我们不一定要用到高级的算法或数据结构知识才能解决问题，数组就足够了。
我没有完成时间/空间复杂度分析，大家可以把它作为课后练习。欢迎大家随时在评论中留言，提出问题或分享观点。
https://hackernoon.com/all-you-need-to-know-about-dynamic-programming-0tj3e5l
【 解决|关于动态规划，你想知道的都在这里了！】本文由AI科技大本营翻译，转载请注明出处