为什么 DFS 内的记忆会导致错误的值？

Question

问题来自leetcode 2976。转换字符串的最低成本 I

问题是我们必须将

source

转换为

target

。我们可以使用

original[i]

并将其替换为

changed[i]

。任何一对

original[k]

和

changed[k]

都可以在

i

处重复，其中

cost[i]

!=

cost[k]

.

source

=

"abcd"

,

target

=

"acbe"

,

original

=

["a","b","c","c","e","d"]

,

 changed

=

["b","c","b","e","b","e"]

,

    cost

=

[ 2,  5,  5,  1,  2, 20]

（最低成本：28）

class Solution {
public:
    long long dfs(int source , int target,vector<vector<pair<int,int>>>& adjMatrix,vector<bool>& currentVisited,vector<vector<long long>>& dp ){
        if(source==target){
            return dp[source][target] = 0;
        }
        if(dp[source][target]!=-1){
            return dp[source][target];
        }
        if(currentVisited[source]){
            return LLONG_MAX;
        }
        long long totalCost = LLONG_MAX;
        currentVisited[source] = true;
        for(int i=0;i<adjMatrix[source].size();i++){
            int child = adjMatrix[source][i].first;
            int cost = adjMatrix[source][i].second;
            auto tempres = dfs(child,target,adjMatrix,currentVisited,dp);
            if(tempres!=LLONG_MAX){
                tempres+=cost;
            }
            totalCost = min(totalCost,tempres);
        }
        currentVisited[source] = false;
        return dp[source][target] = totalCost;
    }
    
    long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
        vector<vector<pair<int,int>>> adjMatrix(26,vector<pair<int,int>>());
        unordered_map<string,int> ump;
        // storing only unique combination 
        for(int i=0;i<original.size();i++){
            string key = "";
            key.push_back(original[i]);
            key.push_back(changed[i]);
            if(ump.count(key)>0){
                ump[key]  = min(ump[key],cost[i]);
            }else{
                ump[key] = cost[i];
            }
        }
        for(auto key: ump){
            adjMatrix[key.first[0]-'a'].push_back({key.first[1]-'a',key.second});
        }
        long long count = 0;
        vector<vector<long long>> dp(26,vector<long long>(26,-1));
        for(int i=0;i<26;i++){
            for(int j=0;j<26;j++){
                vector<bool> currentVisited(26,0);
               dfs(i,j,adjMatrix,currentVisited,dp);
            }
        }
        for(int i=0;i<source.size();i++){
            if(source[i]!=target[i]){
                int cost = dp[source[i]-'a'][target[i]-'a'];
                if(cost==LLONG_MAX){
                    return -1;
                }
                count+=cost;
            }
        }
        return count;
    }
};

dp[source][target] = totalCost;

是一个过早的分配吗？
我的理解是对于每个递归源，因为我们正在遍历它的所有链接，它将被正确分配给每个递归调用。

我知道给定的方法不是最佳的，但我更感兴趣的是了解为什么这份备忘录会出错。

本来希望它能正常工作，但看起来

dp[source][target] = totalCost;

给出了错误的结果。
但如果我回来

totalCost

而是存储

dp[i][j] =  dfs(i,j,adjMatrix,currentVisited,dp);

工作正常。

无法理解为什么第一种情况可能会失败，并且无法提供（最小）示例图，这将导致失败。

Answer 1

Found why this might go wrong . 
if we start function in search for a->b
lets say graph is 
a->c 7
c->a 2 
a->b 1
starting call f(a,b) find path from a to b . and a is marked visited
f(a,b) : can go to(c or b)
    f(c,b): can go to(a)
        f(a,b):
            here a is already visited so LLONG_MAX is returned making it seem that f(c,b) is impossible . But thats not true .
            Issue happened because a was visited already while .So incorrect memo because visited is not allowing to navigate path from c->a->b
            return LLONG_MAX causing f(c,b) to store LLONG_MAX which is incorrect
    f(a,b):
        // will memorise properly f(a,b)