c++ - 无法理解为什么动态编程在这里不起作用

我正在尝试从 leetcode 解决Word Ladder问题。简而言之，它要求您编写通过一次替换一个字母将一个单词转换为另一个单词的代码，以便每个中间字符串也是一个单词。

我知道任何人都可以使用BFS轻松解决它。但是我认为动态编程(dp)技术也可以在这里使用。所以我想用dp解决它。对于每个样本测试用例，它都可以正常工作。但是对于大量输入，此代码将失败(系统判断)。 。

现在还是我不明白为什么dp在这里不起作用？

任何人都可以在失败的情况下给我一点点输入吗？您知道几乎不可能通过this大输入来测试此代码调试。

预先感谢。

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;
    }
};

最佳答案

看来您正在尝试记住DFS。 DFS会在周期中遇到麻烦，这也意味着您必须考虑一个非常短的解决方案，然后才能探索可能很大的搜索空间。

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

关于c++ - 无法理解为什么动态编程在这里不起作用，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57208957/