动态规划问题，下降路径最小和（dp初始化问题，状态压缩），单词拆分（回溯法+剪枝+记忆化），substr函数

下降路径最小和

题目链接：

931. 下降路径最小和 - 力扣（LeetCode）

题目描述：

给你一个 n x n 的方形整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

n == matrix.length == matrix[i].length
1 <= n <= 100
-100 <= matrix[i][j] <= 100

解题思路

这道题算比较简单的一道动态规划问题

我们定义一个同样大小的 dp 数组，dp[i][j] 表示从矩阵的第一行出发，到达 matrix[i][j] 这个位置的最小下落路径和。

dp数组的初始化这里没有什么要求，

basecase为：

对于第一行（i = 0），到达 matrix[0][j] 的最小路径和就是它自身的值，因为它是路径的起点。
因此，初始化 dp[0][j] = matrix[0][j] 对于所有 j 从 0 到 n-1。

这里的状态转移方程也比较明显，题目中提示的比较明显，从下面这幅图中应该也能看出来，橙色格子的值只可能和三个蓝色的格子有关，但是这个状态转移要考虑一下边界 j == 0 或者j == n的情况。

代码实现

#include<bits/stdc++.h>
using namespace std;int minFallingPathSum(vector<vector<int>>& matrix) {int n = matrix.size();//这道题目对dp数组整体初始化没要求，不需要初始化为一个极大值/极小值vector<vector<int>> dp(n, vector<int>(n, 0));//basecase初始化for(int i=0; i<n; i++){dp[0][i] = matrix[0][i];}for(int i=1; i<n; i++){for(int j=0; j<n; j++){if(j == 0){dp[i][j] = min(dp[i-1][j]+matrix[i][j], dp[i-1][j+1]+matrix[i][j]);}else if(j == n-1){dp[i][j] = min(dp[i-1][j-1]+matrix[i][j], dp[i-1][j]+matrix[i][j]);}else{dp[i][j] = min(dp[i-1][j+1]+matrix[i][j], min(dp[i-1][j-1]+matrix[i][j], dp[i-1][j]+matrix[i][j]) );}}}int min_length_val = INT_MAX;for(int i=0; i<n; i++){min_length_val = min(min_length_val, dp[n-1][i]);}return min_length_val;
}int main(){vector<vector<int>> matrix = {{2, 1, 3},{6, 5, 4},{7, 8, 9}};cout << "minFallingPathSum: " << minFallingPathSum(matrix);return 0;
}

关于dp数组初始化问题的解释

在上面下降路径最小和这个问题中，我们说对于dp数组整体初始化的值没有要求。

只需要对dp数组的第一行赋值matrix的第一行（因为这里dp数组的第一行代表着是basecase）。

所以在下降路径最小和这道动态规划问题中，我们的初始化部分只对basecase对应的dp做了赋值，其他非基本情况状态对应的dp状态没有设置。

在上一篇dp文章中的零钱兑换和最长递增子序列问题中，我们还需要专门考虑设计整个dp数组的初始化元素值。这道题为什么就不需要呢？别急，下面我就将来解释一下。

动态规划介绍，零钱兑换，最长递增子序列-CSDN博客

在很多动态规划问题中，我们确实需要将 dp 数组初始化为一个特定的值（例如，求最小值时初始化为 INT_MAX，求最大值时初始化为 INT_MIN，或者根据问题初始化为 0，1 或 -1 来表示状态是否可达/已计算）等。这是因为：

表示不可达或未计算的状态： 有些 DP 问题中，某些状态可能从其他状态无法达到，或者在计算某个状态时，其依赖的前置状态还没有被计算。使用一个特殊值（如 INT_MAX 或 -1）可以明确区分这些状态。
确保取 min/max 操作的正确性： 如果我们要求最小值，并且依赖的状态还没计算（或者不可达），但其初始值为 0，那么 min(当前值, 0) 可能会错误地取到 0，从而影响后续计算。初始化为 INT_MAX 可以保证任何一个实际有效的路径和都会小于 INT_MAX，从而被正确选中。

但是，在这个特定的“最小下落路径和”问题中，使用默认的 0 初始化是可行的，且不会影响结果的正确性。原因如下：

严格的依赖关系和计算顺序： 代码的循环结构是从 i = 1 开始逐行向下计算 dp[i][j] 的值。计算 dp[i][j] 时，它只依赖于 dp 数组中第 i-1 行的值 (dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])。
保证依赖值已被正确计算： 当代码执行到计算第 i 行时，它所依赖的第 i-1 行的所有 dp 值已经在前一个外层循环迭代 (i-1) 中被正确计算并存储过了（要么是 Base Case，要么是基于更早行的计算）。
未使用的值为 0 不影响： 当我们计算 dp[i][j] 时，虽然 dp 数组中第 i 行及之后行的值可能还是默认的 0，但这些值并没有被用于当前 dp[i][j] 的计算。只有第 i-1 行的值被读取，而这些值在前一步已经保证是正确的了。

简而言之，在这个问题中，每一个 dp[i][j] 的计算都严格依赖于前一行已经计算好的值。因此，未被计算到的位置的初始值（在这里是 0）并不会被错误地用来影响当前或后续的正确计算。状态转移方程会作用在每一个dp状态上面，每一个dp状态都会运用状态转移方程进行计算，所以也就不需要对dp数组来进行初始化。

所以本道题中只需要basecase，整个dp数组的初始化不需要。

上面说了一堆，我想表达的是什么呢？

我这里主要想强调一下dp问题中关于dp数组的初始化问题，希望上面做出的一个浅浅的总结，可以帮助大家对于dp问题中dp数组初始化问题有一个更加深入的了解，写代码的时候思路更加清晰，结构更加严谨。

大多数情况下我们突出强调的都是状态定义和寻找状态转移方程，毫无疑问这两个问题确实是最重要的，导致我们可能很多时候会疏忽dp数组元素整体初始化这个事情，但dp数组初始化也有着对应的门道。关于什么时候需要dp数组整体初始化？or整体数组应该初始化成什么值？这些问题，也并不是能用结论直接总结出来的。

我们在拿到一个编程题目之后，需要好好想一下是否需要对dp数组进行整体初始化，以及如果整体初始化的话，初始化的值是什么？

提升的方式还是前面说的：多刷，多学，多练！！！

引入状态压缩（降低空间复杂度）

上面代码实现定义了一个n*n的dp数组保存状态，空间复杂度为O(n^2)，由于当前dp行的状态只依赖于上一行dp的状态，我们可以进行状态压缩（空间优化）。

如果允许我们来修改原二维数组matrix的话，那么其实完全可以将这里对于dp数组的操作转变到对于matrix数组的操作。这样空间复杂度为 O(1)。

如果不能对原二维数组matrix的进行修改的话，我们可以用两个一维数组 prev_dp 和 curr_dp，每个大小为n来实现状态压缩。这样的空间复杂度为O(N)。

prev_dp 存储上一行的最小路径和。
curr_dp 存储当前行的最小路径和。

计算完当前行后，将 curr_dp 的内容复制到 prev_dp，或者交换两个数组的指针，为下一行的计算做准备。

#include<bits/stdc++.h>
using namespace std;int minFallingPathSum(vector<vector<int>>& matrix) {int n = matrix.size();// prev_dp 存储上一行的最小路径和vector<int> prev_dp = matrix[0];// curr_dp 存储当前行的最小路径和vector<int> curr_dp(n);for(int i=1; i<n; i++){for(int j=0; j<n; j++){if(j == 0){curr_dp[j] = min(prev_dp[j]+matrix[i][j], prev_dp[j+1]+matrix[i][j]);}else if(j == n-1){curr_dp[j] = min(prev_dp[j-1]+matrix[i][j], prev_dp[j]+matrix[i][j]);}else{curr_dp[j] = min(prev_dp[j+1]+matrix[i][j], min(prev_dp[j-1]+matrix[i][j], prev_dp[j]+matrix[i][j]) );}}prev_dp = curr_dp; //将当前行的数据变成下一行的“上一行”数据}int min_length_val = INT_MAX;for(int i=0; i<n; i++){min_length_val = min(min_length_val, curr_dp[i]);}return min_length_val;
}int main(){vector<vector<int>> matrix = {{2, 1, 3},{6, 5, 4},{7, 8, 9}};cout << "minFallingPathSum: " << minFallingPathSum(matrix);return 0;
}

对于状态压缩，降低空间复杂度一般是代码编写完成，确保可以完成正常功能之后，最后一步才考虑的事情。通常的空间复杂度优化可以达到降维的效果。但是也不是所有的dp问题都可以优化空间复杂度。

空间优化要求我们对于整个dp数组的状态填充有着比较深刻的了解。

单词拆分

题目链接：

139. 单词拆分 - 力扣（LeetCode）

题目描述：

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同

回溯法解题思路

看到这个题目是要求一个可行解，我首先想到可以使用回溯法，首先这个题目看上去就是一个元素可重复选的排列类问题，很适合使用回溯法来完成。

除此之外动态规划类问题一般都是求最优解（一般有多个可行解），像这种判断是否可以组和成功的问题不是很常见。

所以综合考虑之下，我打算先使用回溯法来试试看。

回溯法实现

很标准的一道无重复元素的排列问题，使用的是经典的回溯法的模板，然后我们额外使用了一个find_flag的变量，用来标识是否找到了一个合法的组和，如果找到了说明以及找到问题的解，那么我们便可以凭借这个变量来进行快速的函数递归调用的返回。

#include<bits/stdc++.h>
using namespace std;void backtrack(bool& find_flag, string& track, string& s, vector<string>& wordDict);bool wordBreak(string s, vector<string>& wordDict) {string track;bool find_flag = false;backtrack(find_flag, track, s, wordDict);return find_flag;
}void backtrack(bool& find_flag, string& track, string& s, vector<string>& wordDict){if(track == s){find_flag = true;return;}if(track.size() > s.size()){return;}for(int i=0; i<wordDict.size(); i++){//做选择track += wordDict[i];//下一层决策树backtrack(find_flag, track, s, wordDict);if(find_flag == true){return;}//撤销选择track.erase(track.size() - wordDict[i].size(), wordDict[i].size());// track -= wordDict[i];}}int main(){string s = "leedcode";vector<string> wordDict = {"leed", "abc", "a", "code"};cout << "isfind: " << wordBreak(s, wordDict);return 0;
}

这个代码取得得效果不是很理想，方法是正确的，但是由于算法的效率问题导致通过不了全部的样例，最终结果如下：

32 / 47 个通过的测试用例

想来确实正常，因为回溯法本来就不是什么高效的算法，并且这里我们还没有进行剪枝操作，自然时间过不去是合理的。

回溯法在最坏情况下的时间复杂度确实是指数型的。它的效率很大程度上依赖于剪枝的效果，而剪枝的效果往往难以保证能将复杂度降到多项式级别。

回溯法的总时间复杂度是 （搜索树中被访问的节点数量）乘以（每个节点上进行的计算开销)

所以回溯法时间复杂度，主要看的就是决策树的节点数。

本题中每个节点会对应下一层决策树的wordDict.size()个节点，题目说1 <= wordDict.length <= 1000，那么上一层决策树的每个节点最多会对应下一层决策树的1000个节点。

然后我们再来看决策树的高度，1 <= s.length <= 300，每条边选择一个子字符串。

回溯算法时间复杂度很难很难计算，这里我们就粗糙地认为最坏情况为1000^300(当然实际上不可能有这么多节点)。

下一步我们尝试来进行剪枝优化~

回溯法+前缀剪枝

通过上面这幅图，我们可以看出来，只有在前缀匹配的情况下，我们才需要接着对于这个决策树进行匹配，所以可以用track中保存的前缀与s前面部分做对比，这样对于前缀不匹配的枝条就可以直接砍掉！

事实上对于track中的前缀来说，我们实际上只需要检查决策树当前层次要加入的wordDict中的字符串wordDict[i]是否和s中的某部分匹配就可以了，因为track中的前面部分一定是匹配成功了s的前缀的才会加入到track，所以实际上我们只需要，将想要加入到track中的这部分前缀与字符串s中对应部分进行匹配就可以。

我们需要加入的逻辑只有一点点，其余代码和上面回溯法一样：

//根据前缀是否匹配来进行剪枝
if( wordDict[i] != s.substr(track.size(), wordDict[i].size()) ){continue;
}

完整代码实现如下：

#include<bits/stdc++.h>
using namespace std;void backtrack(bool& find_flag, string& track, string& s, vector<string>& wordDict);bool wordBreak(string s, vector<string>& wordDict) {string track;//保存当前的字符串路径bool find_flag = false;//当找到一个解后，可以借助find_flag变量快速退出backtrack函数backtrack(find_flag, track, s, wordDict);return find_flag;
}void backtrack(bool& find_flag, string& track, string& s, vector<string>& wordDict){if(track == s){find_flag = true;return;}if(track.size() > s.size()){return;}for(int i=0; i<wordDict.size(); i++){//根据前缀是否匹配来进行剪枝if( wordDict[i] != s.substr(track.size(), wordDict[i].size()) ){continue;}//做选择track += wordDict[i];//做下一层决策backtrack(find_flag, track, s, wordDict);if(find_flag == true){return;}//撤销选择track.erase(track.size() - wordDict[i].size(), wordDict[i].size());// track -= wordDict[i];}}int main(){string s = "leedcode";vector<string> wordDict = {"leed", "abc", "a", "code"};cout << "isfind: " << wordBreak(s, wordDict);return 0;
}

这个代码确实进行了一定的剪枝优化，但是最终的结果为

35 / 47 个通过的测试用例

还是由于算法的效率问题导致通过不了全部的样例，不过不要气馁，加上了上面的剪枝优化我们已经多通过了3个样例，胜利就在眼前！！！！！

回溯法+剪枝+记忆化

为什么仍会超时&解决方案

说实话，你要是让我想，我一个人是想不到可以用到记忆化的方式来继续对于这个问题进行优化的。可能下面的记忆化有一点难理解，但是这个优化的思路是非常值得借鉴与学习的！！！

上面前缀剪枝的代码其实还存在大量的重复计算。

首先，让我们明确在这个 Word Break 问题中的子问题是什么？对于回溯函数 backtrack(find_flag, track, s, wordDict)，它的核心任务是判断：能否将字符串 s 的剩余部分（也就是从 track.size() 索引开始到末尾的部分）通过字典中的单词完全匹配完？

所以，一个子问题可以被定义为：对于原始字符串 s 的子串 s[i...s.size()-1]（从索引 i 开始到末尾），能否将其分割成字典中的单词序列？ 在我的代码中，track.size() 实际上就代表了这个起始索引 i。

假设：wordDict = ["apple", "pen", "applepen"]。

初始状态： track = ""，需要匹配 s[0...12] ("applepenapple")。

无论是通过路径 "apple" + "pen" 还是通过路径 "applepen"，我们都到达了完全相同的状态：track 是 "applepen"，需要解决的子问题是判断 s 从索引 8 开始的剩余部分 "apple" 能否被分割。

这就是重叠子问题：同一个子问题（能否匹配 s[i...s.size()-1]）在回溯树的不同分支中被多次遇到和重复计算。

想必你这时候应该就知道了为什么加上了剪枝之后代码仍然超时叭，嘻嘻！

剪枝解决的是： 在一个给定的状态（例如 track 的长度确定后），只尝试那些立即匹配当前剩余部分前缀的字典单词。

剪枝不解决的是： 即使剪枝后，你仍然可能通过 不同的历史路径 到达 同一个中间状态（同一个 track 长度，对应同一个子问题），然后重复计算该子问题的解。

为什么会导致 TLE？

当字符串 s 很长，并且字典中的单词能够以多种方式组合形成 s 的不同前缀时，回溯树会非常庞大。即使有剪枝，由于重叠子问题的存在，大量的计算是重复的。想象一个字符串 s 全部由 'a' 组成，字典是 ["a", "aa", "aaa"]。计算 s 前缀 "aaaaa" 是否可拆分，可能需要判断 "aaaa" + "a"，"aaa" + "aa"，"aa" + "aaa"，"a" + "aaaa" 等，这里的 "aaaa", "aaa", "aa" 等都是重叠子问题，会被反复计算。当 s 的长度达到几百甚至上千，这种重复计算会导致调用栈过深且计算量呈指数级增长，最终超过时间限制。

如何解决重叠子问题？

记忆化搜索 (Memoization): 在你的回溯函数中，增加一个机制来存储每个子问题（由起始索引 i 定义）的结果。通常用一个数组或哈希表 memo[i] 来记录 s[i...s.size()-1] 是否可分割的结果。在计算一个子问题前，先查找 memo[i]。如果已经计算过，直接返回存储的结果；否则，正常计算，并将结果存储到 memo[i] 中。
动态规划 (Dynamic Programming): 构建一个布尔数组 dp，其中 dp[i] 表示 s[0...i-1] 是否可以被分割。通过迭代的方式，从 dp[0] (空字符串，通常为 true) 开始，计算 dp[1], dp[2], ... 直到 dp[s.size()]。计算 dp[i] 时，遍历所有可能的分割点 j < i，检查 dp[j] 是否为 true 并且 s[j...i-1] 是字典中的单词。这种自底向上的方式天然避免了重复计算。

由于这里我们介绍的是回溯法，所以就在原本代码上面加上记忆化来解决，后面会单独介绍到使用dp的方案。

代码实现

#include<bits/stdc++.h>
using namespace std;void backtrack(unordered_set<string>& memo, bool& find_flag, string& track, string& s, vector<string>& wordDict);bool wordBreak(string s, vector<string>& wordDict) {string track;//保存当前的字符串路径bool find_flag = false;//当找到一个解后，可以借助find_flag变量快速退出backtrack函数unordered_set<string> memo;//记录以及验证的，不可划分匹配的剩余子串backtrack(memo, find_flag, track, s, wordDict);return find_flag;
}void backtrack(unordered_set<string>& memo, bool& find_flag, string& track, string& s, vector<string>& wordDict){if(track == s){find_flag = true;return;}if(track.size() > s.size()){return;}if(memo.count(s.substr(track.size()))==1 ){return;}for(int i=0; i<wordDict.size(); i++){//根据前缀来进行剪枝if( wordDict[i] != s.substr(track.size(), wordDict[i].size()) ){continue;}//做选择track += wordDict[i];//做下一层决策backtrack(memo, find_flag, track, s, wordDict);if(find_flag == true){return;}//撤销选择track.erase(track.size() - wordDict[i].size(), wordDict[i].size());// track -= wordDict[i];}memo.insert(s.substr(track.size()));}int main(){string s = "leedcode";vector<string> wordDict = {"leed", "abc", "a", "code"};cout << "isfind: " << wordBreak(s, wordDict);return 0;
}