带你读《图解算法小抄》二十一、动态规划（7）

带你读《图解算法小抄》二十一、动态规划（6）https://developer.aliyun.com/article/1347957?groupCode=tech_library

12.单词拆分

1）题目描述

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，确定 s 是否可以被拆分为一个或多个字典中的单词。

2）解题步骤

为了确定给定字符串是否可以被拆分为字典中的单词，我们可以使用动态规划的思想来解决问题。

• 定义状态：我们可以将问题转化为对于每个字符串的前缀，判断其是否可以被拆分为字典中的单词。令 dp[i] 表示字符串 s 的前 i 个字符是否可以被拆分为字典中的单词。
  
• 初始状态：根据题目的约束，空字符串可以被认为是可以被拆分的。因此，初始状态为 dp[0] = true。
  
• 状态转移方程：对于每个位置 i，我们需要判断字符串的前缀 s[0:i] 是否可以被拆分为字典中的单词。我们可以遍历从 0 到 i-1 的位置 j，并检查前缀 s[0:j]是否可以被拆分为字典中的单词，以及剩余部分 s[j:i] 是否存在于字典中。即 dp[i] = dp[j] && wordDict.includes(s.substring(j, i))。
  
• 最终解：问题的解即为 dp[n]，其中 n 是字符串 s 的长度。
  

下面是使用动态规划解决单词拆分问题的算法框架：

function wordBreak(s, wordDict) {
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true;  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordDict.includes(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }  return dp[n];
}

13.编辑距离

1）题目描述

给定两个单词 word1 和 word2，计算将 word1 转换为 word2 所需的最小操作次数。

可以对一个单词执行以下三种操作：

• 插入一个字符
  
• 删除一个字符
  
• 替换一个字符
  

2）解题步骤

为了计算将一个单词转换为另一个单词所需的最小操作次数，我们可以使用动态规划的思想来解决问题。

• 定义状态：我们可以将问题转化为对于每个字符对 (i, j)，word1 的前 i 个字符和 word2 的前 j 个字符的最小操作次数。令 dp[i][j] 表示 word1 的前 i 个字符和 word2 的前 j 个字符的最小操作次数。
  
• 初始状态：当一个字符串为空时，需要的操作次数等于另一个字符串的长度。因此，初始状态为 dp[i][0] = i 和 dp[0][j] = j。
  
• 状态转移方程：对于每个字符对 (i, j)，我们需要考虑两种情况：如果 word1[i] 等于 word2[j]，那么我们不需要进行任何操作，即 dp[i][j] = dp[i-1][j-1]。
  
• 如果 word1[i] 不等于 word2[j]，我们可以执行插入、删除或替换操作，我们需要选择其中操作次数最小的那个，即 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。
  
• 最终解：问题的解即为 dp[m][n]，其中 m 是 word1 的长度，n 是 word2 的长度。
  

带你读《图解算法小抄》二十一、动态规划（8）https://developer.aliyun.com/article/1347955?groupCode=tech_library