在编程世界中，递归算法是一种常见的解决问题的方法，但有时它也会导致一些意想不到的问题，尤其是在涉及到函数调用参数的求值顺序时。本文将通过一个具体的算法问题，探讨如何使用动态规划来优化递归算法，并解决参数求值顺序不明确的问题。
面临的问题是LeetCode上的第120题，即给定一个数字三角形，需要找到一条从顶部到底部的路径，使得路径上的数字总和最小。例如，给定以下三角形：
[
[2],
[3, 4],
[6, 5, 7],
[4, 1, 8, 3]
]
从顶部到底部的最小路径和为11（即2 + 3 + 5 + 1 = 11）。
动态规划是解决此类问题的有效方法，因为它涉及到子问题的重复计算。首先尝试使用自顶向下的方法，并使用备忘录（memoization）来存储已经计算过的子问题的结果。
int min_aux(vector<vector<int>> ▵, vector<vector<int>> &lookup, int row, int col) {
if (lookup[row][col] != INT_MIN) {
return lookup[row][col];
}
int c = 0;
if (row == triangle.size() - 1) {
c = triangle[row][col];
} else {
c = min(min_aux(triangle, lookup, row + 1, col), min_aux(triangle, lookup, row + 1, col + 1)) + triangle[row][col];
}
lookup[row][col] = c;
return c;
}
这段代码通过递归地检查两个分支，并选择较小的一个来计算最小路径和。这种方法通过了在线评测，运行时间为17ms，但显然还有改进的空间。
观察备忘录（lookup）的大小与输入相同。但如果能够安排递归路径总是先向左下角移动，那么只需要每行一个槽位。为什么？假设为每行分配并保存两个槽位，分别是LEFT和RIGHT。如果LEFT没有被重新访问，那么RIGHT也不可能被访问。否则，就会违反先选择左下角分支的规则。
int min_aux(vector<vector<int>> ▵, vector<int> &lookup, int row, int col, bool left) {
int c = 0;
if (lookup[row] != INT_MIN) {
c = lookup[row];
lookup[row] = INT_MIN;
return c;
}
if (row == triangle.size() - 1) {
c = triangle[row][col];
} else {
c = min(min_aux(triangle, lookup, row + 1, col, true), min_aux(triangle, lookup, row + 1, col + 1, false)) + triangle[row][col];
}
if (!left) {
lookup[row] = c;
}
return c;
}
添加了一个布尔变量到递归中，以告知被调用者它是否在其父节点的左分支，或者是右分支。注意到一个节点最多被访问两次，一次来自其父节点，另一次来自其左父节点作为其右子节点。在第一次从其左父节点访问时保存值，并在第二次从其父节点访问时清除值。
很高兴地将代码提交到在线评测，却发现它失败了。再次审查了代码，似乎没有出错。最后，通过附加调试器，终于发现了bug。算法只有在左分支递归发生在右分支之前才有效。“min”函数调用的两个参数都是递归函数调用，而它们的执行顺序是未指定的。不幸的是，在这种情况下，右边的先执行了！
修复方法很简单。不是将两个调用放在一起，而是将它们分开。通常，非内联函数作为自然屏障，它们的相对顺序保留为程序顺序定义的顺序。
int l = minimum_aux(triangle, lookup, row + 1, col, true);
int r = minimum_aux(triangle, lookup, row + 1, col + 1, false);
c = min(l, r) + triangle[row][col];
通过这种方法，运行时间减少到了11ms。