2645. 构造有效字符串的最少插入数🔖DP🔖穷举

• 题目：https://leetcode.cn/problems/minimum-additions-to-make-valid-string/

动态规划

DP问题，两个步骤：

1. 状态转移方程

第一项作为边界情况，暂不考虑，从第二项往后看，三项之间的规律:

• 当i-1项>i-2项：需要剪掉一个完整abc整体，即f(i) = f(i-1) - 1
• 其余情况：f(i) = f(i-1) + 2

2. 初始状态

第一项默认填充一个完整的abc

function addMinimum(word: string): number {
  const n = word.length;
  const arr = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) 
    arr[i] = i > 1 && word[i - 2] < word[i - 1] ? arr[i - 1] - 1 : arr[i - 1] + 2
  return arr[n]
};

穷举算法

function addMinimum(word: string): number {
  if (!word.replaceAll('abc', '').length) return 0
  let count = 0;
  for (let i = 0; i < word.length; i++) {
    const curr = word[i]
    const next = i + 1 !== word.length ? word[i + 1] : null
    if (i === 0) {
      if (curr === 'b') {
        count = count + 1
      } else if (curr === 'c') {
        count = count + 2
      }
    }
    if (next) {
      if (curr === 'a') {
        if (next === 'a'){
          count = count + 2
        } else if (next === 'c') {
          count = count + 1
        }
      } else if (curr === 'b') {
        if (next === 'a'){
          count = count + 1
        } else if (next === 'b') {
          count = count + 2
        } 
      } else if (curr === 'c') {
        if (next === 'b') {
          count = count + 1
        } else if (next === 'c') {
          count = count + 2
        }
      }
    } else {
      if (curr === 'b') {
        count = count + 1
      } else if (curr === 'a') {
        count = count + 2
      }
    }
  }
  return count
};