我最近参加了一次技术 OA 面试，偶然发现了这个问题。 我自己能够想出自上而下的记忆方法。但即使我能够找出递归关系，我也很难获得同一问题的自下而上的代码。
问题：
最大可达索引 有一个从 0 开始连续编号的无限整数数组。 在每一步中，指针可以从索引 i 移动到索引 i+j，或者保持在原来的位置。 i 的值从 0 开始。j 的值从 1 开始，每一步 j 都会增加 1。 有一种必须避免的已知索引，称为 badIndex。 确定在给定步数内可以达到的最高索引。 例子 步骤 = 4 坏元素 = 6 指针仅限于 4 步，应避免坏项 6。
• 场景 1：
• 在第一步中，i 从 1 开始。移动 1 个单位到索引 0+1=1 并且 j = 2。
• 在步骤 2 中，移动 2 个单位到索引 1+2=3，且 j = 3。
• 在步骤 3 中，不要移动。否则，指针将向坏项 6 移动 3 个单位。现在 j = 4。
• 在第 4 步，将 4 个单位移动到第 3 + 4 = 7 项。
• 场景 2：
在第 1 步，保持索引 0。现在 j = 2。
• 在步骤 2 中，移动 2 个单位到索引 0+2=2 且 j = 3。
• 在第 3 步，移动 3 个单位到索引 2+3=5 且 j = 4
• 在第 4 步，将 4 个单位移动到索引 5+4=9
所以答案是，最大可达索引是9
我的自上而下方法代码：
class Solution:
def maxIndexAvoidingBadIndex(self, steps, badIndex) -> int:
memo = {}
def dfs(i, j):
# Base cases
if i == badIndex:
return 0
if j == steps + 1:
return i
if (i, j) in memo:
return memo[(i, j)]
result = max(dfs(i + j, j + 1), dfs(i, j + 1))
memo[(i, j)] = result
return result
return dfs(0, 1)
我需要帮助来理解如何导出此问题的自下而上的制表解决方案，谢谢！ 我也只是粘贴我现在想到的自下而上的代码，尽管它不是正确的，仅供参考。
def maxIndexAvoidingBadIndex_BU(self, steps, badIndex):
dp = [0] * (steps + 2)
dp[0] = 0
for j in range(1, len(dp)):
if j + dp[j - 1] != badIndex:
dp[j] = max(j + dp[j - 1], dp[j - 1])
print(dp)
return dp[-1]
我不认为这是一个动态规划问题。如果您不停留在原处，您将通过三角形数字找到索引 1、3、6、10，依此类推。如果 badIndex 是一个三角形数字，您可以通过保持步骤 1 中的位置来最小化错过它。
所以逻辑是：
if istriangular(badindex) {
return n*(n+1)/2 - 1
}
return n*(n+1)/2
其中，当 k 是三角形数时，istriangle(k) 为真。您可以搜索如何有效地实现这一点（有效地 O(1)）。