algorithm - 为什么词梯的动态规划解决方案不起作用？

Question

几天来，当我对单词阶梯问题的解决方案失败时，我一直在努力想出一个简单的案例。我尝试通过内存实现一个DP解决方案。我将不胜感激解释为什么 DP 在这里不起作用。以下是我如何实现我的(不正确的)DP 解决方案。

public class Solution {

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    int[] visited = new int[wordList.size()];
    HashMap<String, Integer> map = new HashMap<>();
    int res = ladderHelper( beginWord,endWord, wordList,visited,map);
    return res;
}

private int ladderHelper(String beginWord, String endWord, List<String> wordList, int[] visited, HashMap<String, Integer> map) {
    if (beginWord.equals(endWord)) return 1;
    int bestSeen = 0;
    for (int i = 0; i < wordList.size(); i++) {
        if (visited[i] == 1) continue;
        if (!validJump(beginWord, wordList.get(i))) continue;
        if (map.containsKey(wordList.get(i))) {
            int val = map.get(wordList.get(i));
            if (val != 0 && val+ 1 < bestSeen) bestSeen = map.get(wordList.get(i))+1;
        }else {
            visited[i] = 1;
            int distance = ladderHelper(wordList.get(i), endWord, wordList, visited, map);
            visited[i] = 0;
            if (distance != 0 && (bestSeen == 0 || distance + 1 < bestSeen)) bestSeen = distance+1;
        }
    }
    map.put(beginWord, bestSeen);
    return bestSeen;
}

private boolean validJump(String a, String b) {
    int mistakes = 0;
    for (int i = 0; i < a.length(); i++) {
        if (a.charAt(i) != b.charAt(i) && ++mistakes > 1) return false;
    }
    return true;
}
}

问题给出的比较详细here .

Answer 1

我认为这段代码有一个微不足道且有趣的问题。

小错误

行内:

if (val != 0 && val+ 1 < bestSeen) bestSeen = map.get(wordList.get(i))+1;

如果 bestSeen 等于 0(如果到目前为止所有值都在缓存中就是这种情况)，则此条件永远不会激活。你需要更多类似的东西:

if (val != 0 && (bestSeen==0 || val+ 1 < bestSeen)) bestSeen = map.get(wordList.get(i))+1;

这样做的效果是有时会忽略较短的路线。

有趣的错误

您正在使用 DFS 来尝试找到最短路径。如果您改用 BFS，我希望您的解决方案能够通过。

DFS 失败的原因是访问数组。 visited 数组用于跟踪当前路径上的单词，以防止无限递归。问题是我们忽略了所有经过这些已访问节点的路径。

乍一看这似乎很好，毕竟我们的最短路径永远不需要自己循环!

但是，请考虑下图表示的单词模式:

假设您的 DFS 代码访问了 A、B、C、D。

当它访问 D 时，它会查看它的邻居，发现它们都被访问过，并得出结论，不可能存在从 D 到终点的路由!

当算法回溯时，最终会尝试路径start->D，但是缓存会报告这条路径不可能，因此不会找到最短路径。