664.奇怪的打印机

链接：664.奇怪的打印机
难度：Hard
标签：字符串、动态规划
简介：给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

题解 1 - typescript

• 编辑时间：2021-05-24
• 执行用时：124ms
• 内存消耗：122.9MB
• 编程语言：typescript
• 解法介绍：动态规划。

function strangePrinter(s: string): number {
  const len = s.length;
  const dp: number[][] = new Array(len).fill(0).map(_ => new Array(len).fill(0));
  for (let i = len - 1; i >= 0; i--) {
    dp[i][i] = 1;
    for (let j = i + 1; j < len; j++) {
      if (s[i] === s[j]) dp[i][j] = dp[i][j - 1];
      else {
        let min = Infinity;
        for (let k = i; k < j; k++) min = Math.min(dp[i][k] + dp[k + 1][j], min);
        dp[i][j] = min;
      }
    }
  }
  return dp[0][len - 1];
}