如何编写网站建设销售的心得,wordpress精美主题,完整网站模板,家电设计网站我们前面看过了0-1背包问题#xff0c;矩阵最短路径长度问题和莱文斯坦最短 编辑距离问题。
在三个问题的状态树中。 0-1背包问题#xff1a;用(i,cw)表示状态。i 表示要将要处理第i个物品#xff0c;cw表示当前总重量。因为(i,cw)有重复的#xff0c;所以使用动态规划。 …我们前面看过了0-1背包问题矩阵最短路径长度问题和莱文斯坦最短 编辑距离问题。
在三个问题的状态树中。 0-1背包问题用(i,cw)表示状态。i 表示要将要处理第i个物品cw表示当前总重量。因为(i,cw)有重复的所以使用动态规划。
矩阵最短路径长度用(i,j,currentPathSum)表示状态。表示当前将要处理第i行第j列的数据在处理之前已经走过的路径长度是currentPathSum。因为在(i,j)状态下有不同的currentPathSum我们只需要留下最小的currentPathSum即可。
莱文斯坦问题用(i,j,edist)表示状态i表示指针在a字符串的位置j表示指针在b字符串的位置(i,j)都表示将要处理的字符位置edist表示到达(i,j)时已经执行的编辑次数。因为在(i,j)状态下有不同的edist我们只需要留下最小的edist即可。
矩阵最短路径长度的目标是要找到最小的长度所以在每个状态只保留最小的长度。 莱文斯坦问题的目标是要找到最小的编辑距离所以在每个状态只保留最小的编辑距离。 0-1背包问题目标是求最大的重量为什么不只保留最大的重量就可以呢因为0-1背包问题的限制条件也是重量。它要求总重量不能超过w。所以每一步决策之后的重量都有可能是一个结果。所以不能剪裁需要保留。
