固定最优求解顺序 （我们称之为Foo方法）：Foo方法通常从子问题开始，逐步求解更大的问题，因此使用先前获得的子问题的结果来解决更大的问题，从而避免“重复计算”子问题。 CLRS 似乎也将其称为“自底向上”方法。
没有固定的最优求解顺序（我们称之为非Foo方法）：在这种方法中，求解从问题到它们的子问题进行，确保子问题没有被“重新计算”（从而确保最优性），通过在某些数据结构中维护以前评估结果的结果，然后首先检查手头问题的结果是否存在于该数据结构中，然后再开始评估。 CLRS似乎将其称为“自顶向下”方法
我有以下疑问：
Q1. 有无记忆化？
CLRS使用术语“自顶向下带记忆化”方法和“自底向上”方法。我认为这两种方法都需要内存来缓存子问题的结果。但是，然后，为什么CLRS仅针对自顶向下方法而不是针对自底向上方法使用术语“记忆化”？通过使用DP方法解决一些问题，我发现对于所有问题，自顶向下方法的解决方案都需要内存来缓存所有子问题的结果。然而，自底向上方法并非如此。自底向上方法的某些问题的解决方案不需要缓存所有子问题的结果。 Q1. 我的理解是否正确？
例如，考虑此问题：自顶向下的解决方案如下：给定一个楼梯上每个阶梯的成本cost[i]，如果：
- 您可以爬上一步或两步
- 您可以从索引0或索引1的步骤开始
请给出到达地板顶部的最小成本。
class Solution:
def minCostAux(self, curStep, cost):
if self.minCosts[curStep] > -1:
return self.minCosts[curStep]
if curStep == -1:
return 0
elif curStep == 0:
self.minCosts[curStep] = cost[0]
else:
self.minCosts[curStep] = min(self.minCostAux(curStep-2, cost) + cost[curStep]
, self.minCostAux(curStep-1, cost) + cost[curStep])
return self.minCosts[curStep]
def minCostClimbingStairs(self, cost) -> int:
cost.append(0)
self.minCosts = [-1] * len(cost)
return self.minCostAux(len(cost)-1, cost)
从下往上的方法解决方案如下：
class Solution:
def minCostClimbingStairs(self, cost) -> int:
cost.append(0)
secondLastMinCost = cost[0]
lastMinCost = min(cost[0]+cost[1], cost[1])
minCost = lastMinCost
for i in range(2,len(cost)):
minCost = min(lastMinCost, secondLastMinCost) + cost[i]
secondLastMinCost = lastMinCost
lastMinCost = minCost
return minCost
请注意，自顶向下的方法将所有步骤的结果缓存到
self.minCosts中，而自底向上的方法仅将最后两个步骤的结果缓存在变量lastMinCost和secondLastMinCost中。Q2. 是否所有问题都可以通过这两种方法得出解决方案？
我认为不是。我得出这个结论是在解决这个问题之后：
找出马在
n x n 的棋盘上经过 k 步后不会跑出边界的概率，假设马最初在位置 (row, column)。我认为解决此问题的唯一办法是从初始位置
(row,column)开始逐步增加步数，逐步计算马在走了1步、2步、3步...k步后未跑出棋盘的概率，这就是自底向上的方法。我们不能使用自顶向下的方法，例如无法从第k步开始倒推至k-1步，再倒推至k-2步等，因为：1. 我们不知道第k步时哪些位置可以到达 2. 我们不能确保从第k步出发的所有路径都可以回到起始位置
(row,column)
甚至在最赞的答案中，也有一个给出dp解决方案的例子：class Solution {
private int[][]dir = new int[][]{{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};
private double[][][] dp;
public double knightProbability(int N, int K, int r, int c) {
dp = new double[N][N][K + 1];
return find(N,K,r,c);
}
public double find(int N,int K,int r,int c){
if(r < 0 || r > N - 1 || c < 0 || c > N - 1) return 0;
if(K == 0) return 1;
if(dp[r][c][K] != 0) return dp[r][c][K];
double rate = 0;
for(int i = 0;i < dir.length;i++) rate += 0.125 * find(N,K - 1,r + dir[i][0],c + dir[i][1]);
dp[r][c][K] = rate;
return rate;
}
}
我认为这仍然是一种自底向上的方法，因为它从初始骑士单元格位置 (r,c) 开始（因此从第 0 步或无步开始，到第 K 步），尽管它将 K 从上往下数到 0。因此，这是递归地完成的自底向上的方法，而不是自顶向下的方法。确切地说，该解决方案没有首先找到：
- 在单元格
(r,c)起始，在经过K步后骑士未离开棋盘的概率
然后再找：
- 在单元格
(r,c)起始，在经过K-1步后骑士未离开棋盘的概率
但是，它按相反/自底向上的顺序查找：首先查找 K-1 步，然后查找 K 步。
此外，在 LeetCode 的热门讨论中未发现任何真正的自顶向下方法的解决方案，都是从单元格 (row,column) 开始，而不是从第 K 步开始，直到第 0 步结束在单元格 (row,column)。
同样，我们不能使用自底向上的方法解决以下问题，只能使用自顶向下的方法：
找到骑士在任何初始单元格出发后，经过 K 步后最终在索引为
(row,column)的单元格中的概率。
Q2. 那么我是否正确地理解了并非所有问题都可以通过自顶向下或自底向上的方法进行解决？还是说我过度思考了，两个以上的问题确实可以通过自顶向下和自底向上的方法解决？
PS: 我确实觉得我过度思考了：上面的 knightProbability() 函数确实是自顶向下的，正如上文所解释的那样。我将此解释保留供参考，因为下面已经有一些答案，同时也作为混淆/误解可能发生的提示，以便我将来会更加谨慎。如果这个长说明导致了您的一些混淆/挫败，我很抱歉。无论如何，主要问题仍然存在：每个问题都有自底向上和自顶向下的解决方案吗？
Q3. 自底向上的方法递归实现？
我在考虑是否对所有问题都可以进行自底向上的递归实现。在尝试其他问题时，我得出以下结论：
例如，下面是递归自底向上的解决方案，用于在Q1中提到的爬楼梯问题中寻找最小代价：我们可以递归地实现这些问题的自底向上解决方案，但递归不会有意义，而是有点巧妙。
class Solution:
def minCostAux(self, step_i, cost):
if self.minCosts[step_i] != -1:
return self.minCosts[step_i]
self.minCosts[step_i] = min(self.minCostAux(step_i-1, cost)
, self.minCostAux(step_i-2, cost)) + cost[step_i]
if step_i == len(cost)-1: # returning from non-base case, gives sense of
# not-so meaningful recursion.
# Also, base cases usually appear at the
# beginning, before recursive call.
# Or should we call it "ceil condition"?
return self.minCosts[step_i]
return self.minCostAux(step_i+1, cost)
def minCostClimbingStairs(self, cost: List[int]) -> int:
cost.append(0)
self.minCosts = [-1] * len(cost)
self.minCosts[0] = cost[0]
self.minCosts[1] = min(cost[0]+cost[1], cost[1])
return self.minCostAux(2, cost)
我的理解是正确的吗？