无法理解为什么动态规划在这里不起作用

Question

我正在尝试解决Leetcode的 单词阶梯问题。简而言之，题目要求你编写代码，通过每次替换一个字母将一个单词转换为另一个单词，使得每个中间字符串也是一个单词。

我知道使用BFS算法任何人都可以轻松解决它。但我认为动态规划（DP）技术在这里也可以发挥作用。因此，我尝试使用DP解决它。对于每个样例测试用例，它都运行良好。但是当输入变大时（系统评测），该代码会失败。

到目前为止，我仍然不明白为什么DP不能在这里起作用？

请问有人能给我一个小的输入，让这个代码失败吗？你知道很难通过这个大输入进行调试。

提前感谢。

class Solution {
public:
    vector<int> dp;
    int n;

    bool isOneDiff(string str1, string str2) {
        if(str1.length() != str2.length()) return false;
        int len = str1.length();
        int cnt = 0;
        for(int i = 0; i < len; i++) {
            if(str1[i] != str2[i]) cnt++;
        }
        return cnt == 1;
    }

    int solve(string cur, int ind, const string endWord, vector<string> wordList) {
        if(cur == endWord) return 1;
        int &ret = dp[ind];
        if(ret != -1) return ret;
        ret = 100000000;    // Infinity
        for(int i = 0; i < n; i++) {
            if(isOneDiff(cur, wordList[i])) {
                ret = min(ret, 1 + solve(wordList[i], i, endWord, wordList));
            }
        }
        return ret;
    }
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        n = wordList.size();
        dp.clear();
        dp.resize(n+2, -1);
        int res = solve(beginWord, n, endWord, wordList);
        if(res >= 100000000) return 0;  // if res is greater than or equal to infinity then I have to return 0
        return res;
    }
};

- Faruk Hossain

---

DP解决方案对于这个问题非常低效。如果您只需要从源状态到目标状态的最短路径，为什么需要遍历整个递归树呢？ - mangusta

我会首先从算法上入手，然后再考虑技术方案，无论是动态的还是其他的。 - tadman

是的，在这里使用dp解决方案非常低效。但是“除了一些递归路径可能甚至不会到达目标状态，因此它们永远不会返回”。我不明白你试图理解我的内容。难道我们在解决这个问题时不是创建与BFS相同的路径吗？ - Faruk Hossain

抱歉之前的评论，我已经删除了。在这个问题中根本无法应用动态规划，因为递归树存在循环。记忆化状态也没有意义，因为任何缓存的状态都可能在下一次调用时失效。 - mangusta

@MattTimmermans 你为什么认为BFS是DP？ - mangusta

Answer 1

看起来你正在尝试记忆化深度优先搜索。在循环中，DFS会遇到麻烦，并且这意味着您必须探索可能很大的搜索空间，然后才考虑非常短的解决方案。

顺便说一句，我不建议使用BFS解决此问题。相反，我建议使用A*搜索。

- btilly

---

谢谢您的建议。我会尝试一下。 - Faruk Hossain