动态规划和回溯算法的思维转换 :: labuladong的算法小抄

[giscus[bot]]

动态规划和回溯算法的思维转换 :: labuladong的算法小抄

https://labuladong.github.io/algo/di-er-zhan-a01c6/dong-tai-g-a223e/dong-tai-g-f0a05/

[bruceeewong]

感谢东哥，还是很有帮助。自己做题的时候还是不擅长定义dp函数/数组，总是走到回溯的思路里，然后发现一些情况超时。这篇文章给了回溯和分解问题的思维转换，意识到回溯再遇到重复子问题的时候无能为力，还是得利用动态规划来优化。希望自己慢慢体悟吧哈哈

[CarlLy7]

打卡，感觉东哥，跟着东哥学算法

[CarlLy7]

感谢

[HFESimon]

第一题单词拆分部分：使用分解问题的思路解决题目。对于dp方法的定义，方法签名有些问题；
应为：

// 定义：返回 s[i..] 是否能够被拼出
boolean dp(String s, int i);
// 计算整个 s 是否能被拼出，调用 dp(s, 0)

[luofuliang]

if (i == s.length()) {
res.add("");
return res;
}
请问这里的res.add("");的作用是啥？

[BenjaminChoou]

                    if sub == "":
                        # 防止多余的空格
                        res.append(prefix)

我理解就是为了判断这个用的。

[HFESimon]

您好，邮件已收到！

[ninja119347]

无重可复选的全排列代码，东哥弄错了吧，应该不用visited数组

[HFESimon]

您好，邮件已收到！

[PeisongHao]

回溯算法还没看, 根据我自己对前面动态规划理解写的一个单词拆分的解，快一些, 但不知道快在哪里,可以有大佬帮忙看下吗，谢谢
class Solution {
int[][] memo;
private boolean dp(String s,int i,List wordDict,int j){
String word = wordDict.get(j);
if(s.length() - i < word.length()){
return false;
}
for(int k = 0; k < word.length(); k++){
if(s.charAt(i+k) != word.charAt(k)){
return false;
}
}
if(i + word.length() == s.length()){
return true;
}
if(memo[i][j] != -1){
if(memo[i][j] == 1){
return true;
}else{
return false;
}
}
boolean res = false;
for(int l = 0; l < wordDict.size(); l++){
res = res || dp(s, i + word.length(), wordDict,l);
}
if(res == true){
memo[i][j] = 1;
}else {
memo[i][j] = 0;
}
return res;
}
public boolean wordBreak(String s, List wordDict) {
memo = new int[s.length()][wordDict.size()];
for(int i = 0; i < s.length(); i++){
Arrays.fill(memo[i],-1);
}
boolean res = false;
for(int l = 0; l < wordDict.size(); l++){
res = res||dp(s,0, wordDict,l);
if(res == true){
break;
}
}
return res;
}
}

[HFESimon]

您好，邮件已收到！

[icyrain11]

东哥你好,请问单词拆分二dp的这个写法的作用是什么,可以方便解答下吗,谢谢!

   if (s.length() == i) {
            res.add("");
            return res;
     }