13｜动态规划算法设计的关键：最优子结构与状态依赖
卢誉声
你好，我是卢誉声。
还记得我们曾经讨论过的吗？动态规划是运筹学上的一种最优化方法，常出现在数学、管理科学、计算机科学、经济学和生物信息学中，特别是在算法问题上应用广泛。当我们求解一个复杂问题时，会考虑把原问题分解为相对简单的子问题，再进行求解。
从这个意义上说，动态规划是一种思想，而非传统意义上的算法：如果我们要求解原问题，就需要求解其不同部分（即子问题），再根据子问题的解推导计算出原问题的解。
在专栏中，我们曾反复提及动态规划三大特征，即重叠子问题、无后效性和最优子结构。只有当原问题满足以上特征时，我们才能使用动态规划思想来进行求解。动态规划对子问题与原问题的关系、子问题之间的依赖关系这两方面有一些要求，它们分别对应了最优子结构和重叠子问题。
相较于重叠子问题和无后效性来说，理解最优子结构要稍微困难一些。最优子结构最终决定了我们求解动态规划问题的状态转移过程，甚至是动态规划算法的计算方向。因此，充分理解最优子结构的概念至关重要。
今天，就让我们深入挖掘最优子结构这个概念，以及它与计算方向之间的关系。
深入理解最优子结构
动态规划思想在求解包含重叠子问题情况的最优解时特别有效。它将问题重新组合成子问题，为了避免重复计算，我们会设计一个状态存储，即备忘录来保存中间计算状态。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
动态规划算法设计的关键在于最优子结构和状态依赖。动态规划是一种思想，通过将原问题分解为相对简单的子问题，并根据子问题的解推导计算出原问题的解。最优子结构是动态规划问题的核心，决定了状态转移方程，即子问题的最优解决定了原问题的最优解。动态规划适用于含有重叠子问题和最优子结构性质的问题，能够消除重复计算，加快算法执行速度。最优子结构是某些问题的特定性质，是动态规划问题的必要条件。在确定动态规划解法前，需要判定原问题是否存在最优子结构。最优子结构的定义决定了动态规划算法的计算方向，即状态转移方向。通过子问题求得最终答案的过程，使用状态转移方程进行描述。最优子结构的深入理解有助于确定状态转移方程的正确性。 文章还提到了动态规划问题的计算方向，强调了子问题之间的依赖必须是单向的，且计算方向的确定与最优子结构和状态转移方程的设计有直接关系。文章以“最长回文子序列”问题为例，说明了在动态规划中计算方向的重要性，并指出了正确的计算方向对于写出正确的循环迭代代码的重要性。 最后，文章提出了一个动态规划问题“编辑距离”，并邀请读者分析其中的最优子结构。总结来看，本文通过讲解动态规划算法设计的关键，以及计算方向的重要性，帮助读者深入理解动态规划问题的解决方法。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《动态规划面试宝典》，新⼈⾸单¥59
《动态规划面试宝典》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(6)
- 最新
- 精选
IT蜗壳-Tango
打卡学习作者回复: gogogo
2020-11-053- Geek_b5f791java解法： public int minDistance(String word1, String word2) { int n = word1.length(); int m = word2.length(); //任意一个字符串为空就返回另一个字符串的长度 if (n * m == 0) { return n + m; } //初始化状态 dp[i][j]表示 从word1的第i个字符变到word2的第j个字符时的变化数 int[][] dp = new int[n + 1][m + 1]; dp[0][0] = 0; for (int i = 0; i <= n; i++) { dp[i][0] = i; } for (int j = 0; j <= m; j++) { dp[0][j] = j; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { //dp[i - 1][j]到dp[i][j]是insert、dp[i][j - 1]是delete、dp[i - 1][j - 1]是replace //replace时 如果相等 说明不用 dp[i][j] = Math.min(Math.min(dp[i - 1][j]+1, word1.charAt(i - 1) == word2.charAt(j - 1) ? dp[i - 1][j - 1] : dp[i - 1][j - 1]+ 1),dp[i][j - 1]+1) ; } } return dp[n][m]; }
作者回复: 解决方案是正确的。
2021-04-132 
第一装甲集群司令克莱斯特学透动态规划！作者回复: 加油！
2020-11-131
BBQ编辑距离的状态转移方程 def minDistance(self, word1: str, word2: str) -> int: if not word1 and not word2: return 0 if not word1 or not word2: return len(word1) if word1 else len(word2) h, w = len(word1), len(word2) dp = [[0] * (w+1) for _ in range((h+1))] #加上空字符作为哨兵节点 for i in range(1, len(dp[0])): dp[0][i] = dp[0][i-1] + 1 #初始化第一行，空字符到达每一个非空字符都是+1 for i in range(1, len(dp)): dp[i][0] = dp[i-1][0] + 1 #初始化第一列，空字符到达每一个非空字符都是+1 for i in range(1, len(dp)): for j in range(1, len(dp[0])): if word1[i-1] == word2[j-1]: #相等，编辑距离不增加 dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(dp[i-1][j], dp[i][j-1],dp[i-1][j-1]) + 1 # dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作 return dp[-1][-1]作者回复: 解法没有问题，清晰明了！顶上去，让更多人看到。
2021-03-12
小嘟嘟class Solution { public: int minDistance(string word1, string word2) { if(word1.empty()) return word2.size(); if(word2.empty()) return word1.size(); int n1 = word1.size(); int n2 = word2.size(); vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0)); // dp[i][j] 含义， word1的前i个字符 转化成word2的前j字符最少操作数 // 状态初始化 for(int i = 0; i <= n1; i++){ dp[i][0] = i; } for(int i = 0; i <= n2; i++){ dp[0][i] = i; } for(int i = 1; i <= n1; i++){ for(int j = 1; j <= n2; j++){ if(word1[i-1] == word2[j-1]){ dp[i][j] = dp[i-1][j-1]; }else{ dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1],dp[i-1][j])) + 1; } } } return dp[n1][n2]; } }; 此刻刚刚昨晚“编辑距离”， 贴代码留个脚印作者回复: 恩，没有问题。
2021-03-05
panbook总结的透彻清晰，受益匪浅，好多地方都重点划线了作者回复: 你的肯定就是我最大的动力。谢谢你的反馈。
2021-01-23
收起评论
