search

lucifer1004 / cp-wiki

lucifer1004 的 CP 笔记
https://cp-wiki.vercel.app
130 stars 15 forks source link

Leetcode 第205场周赛题解 #14

Open utterances-bot opened 3 years ago

utterances-bot commented 3 years ago

Leetcode 第205场周赛题解 | CP Wiki

parent[i] = i; }

https://cp-wiki.vercel.app/tutorial/leetcode/WC205/

Afrankie commented 3 years ago

大佬，我问一个很傻的问题，Problem C的14行，为什么只更新 第i位，结尾为c的最小成本，而不需要以同样的方式更新以其他结尾的状态

lucifer1004 commented 3 years ago

@Afrankie 因为非c结尾的，只能来自上一次的非c；而c结尾的，可以来自上一次除了c之外的任何一种情况。所以这两个转移的处理是不同的。

Afrankie commented 3 years ago

抱歉我没说清楚，我的意思是下面这样

for (int j = 0; j < 26; ++j) {
    ndp[j] = min(ndp[j], dp[j] + cost[i - 1]);
    for (int k = 0; k < 26; k ++) {
        if (j != k) {
            ndp[j] = min(ndp[j], dp[k]);
        }
    }
}
lucifer1004 commented 3 years ago

@Afrankie 这样就错了啊，并不能任意地从dp[k]转移到ndp[j]，因为只有j==c时才能进行这种转移。

Afrankie commented 3 years ago

谢谢大佬🙏，我明白了，我理解错了，我是写java的所以看到第8行代码

for (int i = 1; i <= n; ++i)

第一反应就是状态从第二个字符开始，那么自然的把第10行的c当作是第i个字符的上一个字符，所以一直不懂为什么以其他结尾的状态只能转移到当前的以c结尾的状态，现在明白了，如果转移到除c之外的字符就是不符合逻辑的。 没注意到 i <= n，这也能说明不是从第二个字符开始