动态规划

322. 零钱兑换

details

/**
 * 322. 零钱兑换
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
  function dp(n) {
    if (n < 0) return -1;
    if (n <= 0) return 0;

    let ans = Number.MAX_SAFE_INTEGER;
    for (const coin of coins) {
      let subProblem = dp(n - coin);
      if (subProblem === -1) {
        continue;
      }
      ans = Math.min(ans, 1 + subProblem);
    }
    return ans !== Number.MAX_SAFE_INTEGER ? ans : -1;

}

return dp(amount);
};

/\*\*

-   备忘录
-   自顶向下
    \*/

var coinChange1 = function(coins, amount) {
let map = Object.create(null);

function dp(n) {
if (map[n]) return map[n];
if (n < 0) return -1;
if (n <= 0) return 0;

    let ans = Number.MAX_SAFE_INTEGER;
    for (const coin of coins) {
      const subProblem = dp(n - coin);
      if (subProblem === -1) {
        continue;
      }
      ans = Math.min(ans, 1 + map[n - coin]);
    }
    map[n] = ans !== Number.MAX_SAFE_INTEGER ? ans : -1;
    return map[n];

}

return dp(amount);
};

/\*\*

-   dp 表
-   自底向上
    \*/

var coinChange2 = function(coins, amount) {
const dp = new Array(amount + 1).fill(amount + 1);
dp[0] = 0;

let i = 0;
while (i < dp.length) {
for (const coin of coins) {
// 子问题无解
if (i - coin < 0) {
continue;
}
console.log(dp[i - coin]);
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
}
i++;
}
return dp[amount] === amount + 1 ? -1 : dp[amount];
};

coinChange2([1, 2, 5], 11);

剑指 Offer 10- I. 斐波那契数列

details

/**
 * 剑指 Offer 10- I. 斐波那契数列
 * 递归 O(2^n)
 * @param {*} n
 * @returns
 */

function fib(n) {
  if (n <= 0) return 0;
  if (n === 1 || n === 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

/**
 * 缓存 O(n)
 * 空间复杂度 O(n)
 */

function fib2(n) {
  if (n === 0) return 0;
  const map = {};
  return helper(map, n);
}
function helper(map, n) {
  if (n === 1 || n === 2) return 1;
  if (map[n]) return map[n];
  map[n] = (helper(map, n - 1) + helper(map, n - 2)) % 1000000007;
  return map[n];
}

/**
 * 动态规划 O(n)
 * 空间复杂度 O(n)
 */

function fib3(n) {
  if (n <= 0) return 0;
  if (n <= 2) return 1;
  const dp = [0, 1, 1];
  let i = 3;

  while (i <= n) {
    dp[i] = dp[i - 1] + dp[i - 2];
    i++;
  }
  return dp[n];
}

/**
 * 缓存 O(n)
 * 空间复杂度 O(1)
 */
function fib4(n) {
  if (n <= 0) return 0;
  if (n <= 2) return 1;
  let i = 3;

  let ans = 1;
  let pre = 1;

  while (i <= n) {
    const sum = pre + ans;
    pre = ans;
    ans = sum;
    i++;
  }
  return ans;
}

console.log(fib4(3));

300. 最长递增子序列

details

/**
 * 300. 最长递增子序列
 * @param {number[]} nums
 * @return {number}
 */

// 时间复杂度 O(n^2)
// 空间复杂度 O(n)
var lengthOfLIS = function(nums) {
const len = nums.length;
if (len <= 1) return 1;

const dp = new Array(len).fill(1);

let i = 0;
while (i < len) {
const char = nums[i];
let j = 0;
// console.log(dp)
while (j < i) {
if (char > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
j++;
}
i++;
}
return Math.max(...dp);
};

// 基于扑克 排序
// 时间复杂度 O(nlogn)
// 空间复杂度 O(n)
var lengthOfLIS2 = function(nums) {
const len = nums.length;
if (len <= 1) return 1;
// 初始化状态为 0
const top = new Array(len).fill(0);
//
let piles = 0;
for (let i = 0; i < len; i++) {
const cur = nums[i];

    // 二分查找左边界
    let left = 0;
    let right = piles;
    while (left < right) {
      const mid = left + (((right - left) / 2) >> 0);
      if (top[mid] > cur) {
        right = mid;
      } else if (top[mid] < cur) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    if (left === piles) {
      piles++;
    }
    top[left] = cur;
    // console.log(top, left);

}
return piles;
};

354. 俄罗斯套娃信封问题

details

var maxEnvelopes = function(envelopes) {
  // 边界值
  const len = envelopes.length;
  if (len <= 1) return len;

  // 先排序
  envelopes.sort((a, b) => {
    if (a[0] > b[0]) {
      return 1;
    }
    if (a[0] === b[0]) {
      return b[1] - a[1];
    }
    return -1;
  });

  // 再对 b 做 lis
  return lengthOfLIS(envelopes.map(item => item[1]));

  function lengthOfLIS(nums) {
    const len = nums.length;
    if (len <= 1) return 1;
    // 初始化状态为 0
    const top = new Array(len).fill(0);
    //
    let piles = 0;
    for (let i = 0; i < len; i++) {
      const cur = nums[i];

      // 二分查找左边界
      let left = 0;
      let right = piles;
      while (left < right) {
        const mid = left + (((right - left) / 2) >> 0);
        if (top[mid] > cur) {
          right = mid;
        } else if (top[mid] < cur) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      if (left === piles) {
        piles++;
      }
      top[left] = cur;
      // console.log(top, left);
    }
    return piles;
  }
};

53. 最大子数组和

details


var maxSubArray = function (nums) {
const len = nums.length;
if (len <= 1) return nums[0];
const dp = new Array(len).fill(-Number.MAX_SAFE_INTEGER);

    let i = 1;
    dp[0] = nums[0];

    while (i < len) {
        dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
        i++;
    }
    return Math.max(...dp);

};

var maxSubArray2 = function (nums) {
const len = nums.length;
if (len <= 1) return nums[0];

    let i = 1;
    let pre = nums[0];
    let ans = pre;
    while (i < len) {
        pre = Math.max(nums[i], pre + nums[i]);
        ans = Math.max(pre, ans);
        i++;
    }
    return ans;

};

1312. 让字符串成为回文串的最少插入次数

details

/**
 * 1312. 让字符串成为回文串的最少插入次数
 * @param {string} s
 * @return {number}
 */
var minInsertions = function(s) {
  const len = s.length;
  if (len <= 1) return 0;
  // 定义dp[i,j] 为 s[i,j]最少插入 dp[i,j]次才能变成回文
  const dp = new Array(len).fill(0).map(() => new Array(len).fill(0));

let i = len - 2;
while (i >= 0) {
let j = i + 1;
while (j < len) {
// console.log(dp)
if (s[i] === s[j]) {
dp[i][j] = dp[i + 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
j++;
}
i--;
}
return dp[0][len - 1];
};

198. 打家劫舍

只有 1 家只有 2 家超过 2 家

dp 定义为打劫当前家能获取到的最大值

Javascript

var rob = function (nums) {
    if (nums.length === 0) return 0;
    const len = nums.length;
    if (len === 1) return nums[0];
    const dp = new Array(len).fill(0);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (let i = 2; i < len; i++) {
        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
    }
    return dp[len - 1];
};

优化方案 通过以上分析可知，我们只需要知道当前 index 的前 2 个 index-1 index-2 的值即可，所以，空间复杂度可以优化为 O(1)

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
    if (nums.length === 0) return 0;
    const len = nums.length;
    if (len === 1) return nums[0];

    let first = nums[0],
        second = Math.max(nums[0], nums[1]);

    for (let i = 2; i < len; i++) {
        let temp = second;
        second = Math.max(first + nums[i], second);
        first = temp;
    }
    return second;
};

213. 打家劫舍 II

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
    const len = nums.length;
    if (len === 1) return nums[0];
    if (len === 2) return Math.max(nums[0], nums[1]);
    return Math.max(robRange(nums, 0, len - 2), robRange(nums, 1, len - 1));

    function robRange(nums, start, end) {
        let first = nums[start],
            second = Math.max(nums[start], nums[start + 1]);
        for (let i = start + 2; i <= end; i++) {
            const temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
};

这道题是树形 DP 的题目，因此可以使用递归来求解。我们可以用一个长度为 2 的数组来表示某个节点是否被选择，具体地，dp[i][0] 表示节点 i 不被选择的最大值，dp[i][1] 表示节点 i 被选择的最大值。我们可以通过递归求解某个节点的 dp 值，具体地，对于当前节点 i，如果不选择它，那么最大值即为左右子节点选择或不选择的最大值之和，即 dp[i][0] = max(dp[l][0], dp[l][1]) + max(dp[r][0], dp[r][1])；如果选择它，那么左右子节点不能被选择，因此最大值为左右子节点不被选择的最大值加上当前节点的权值，即 dp[i][1] = dp[l][0] + dp[r][0] + val[i]。

可以层序遍历出每层的值，转化为打家劫舍问题一，时间复杂度(2n) 空间复杂度 O(h) h 为树的深度，极端情况为 n

Javascript

var rob = function (root) {
    function dp(node) {
        if (!node) {
            return [0, 0];
        }
        const [l0, l1] = dp(node.left);
        const [r0, r1] = dp(node.right);
        const dp0 = Math.max(l0, l1) + Math.max(r0, r1);
        const dp1 = l0 + r0 + node.val;
        return [dp0, dp1];
    }

    const [root0, root1] = dp(root);
    return Math.max(root0, root1);
};

96. 不同的二叉搜索树

题目要求计算以 1 到 n 为节点组成的所有二叉搜索树的数量，这是一个数学问题，其结果是卡特兰数。可以使用动态规划解决这个问题，具体做法如下：

定义状态：设 f(n) 为以 1 ... n 为节点组成的二叉搜索树的个数。
初始化：当 n=0 时，空树的个数为 1。
状态转移：当 n>0 时，对于每一个 i∈[1,n]，以 i 为根节点的二叉搜索树数量为左子树的数量乘以右子树的数量，即 f(i-1) * f(n-i)，将所有的以 i 为根节点的二叉搜索树的数量相加就是 f(n) 的值。
返回值：f(n) 即为所求。

Javascript

function numTrees(n) {
    // 定义状态数组
    const dp = new Array(n + 1).fill(0);
    // 初始化
    dp[0] = 1;
    // 状态转移
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= i; j++) {
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    // 返回结果
    return dp[n];
}

方法二：数学卡塔兰数

Javascript

var numTrees = function (n) {
    let C = 1;
    for (let i = 0; i < n; ++i) {
        C = (C * 2 * (2 * i + 1)) / (i + 2);
    }
    return C;
};

95. 不同的二叉搜索树 II

Javascript

/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function (n) {
    let ans = [];
    if (n == 0) return ans;
    return generateTreesDFS(1, n);

    function generateTreesDFS(start, end) {
        if (start > end) return [null];
        const trees = [];
        for (let i = start; i <= end; i++) {
            const leftTrees = generateTreesDFS(start, i - 1);
            const rightTrees = generateTreesDFS(i + 1, end);
            for (const leftTree of leftTrees) {
                for (const rightTree of rightTrees) {
                    trees.push(new TreeNode(i, leftTree, rightTree));
                }
            }
        }
        return trees;
    }
};

509. 斐波那契数

Javascript

var fib = function (n) {
    if (n < 2) return n;

    let first = 0,
        second = 1;
    for (let i = 2; i <= n; i++) {
        let cur = first + second;
        first = second;
        second = cur;
    }
    return second;
};

剑指 Offer 10- I. 斐波那契数列

动态规划

Javascript

/**
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
    if (n < 2) return n;

    let first = 0,
        second = 1;
    for (let i = 2; i <= n; i++) {
        let cur = (first + second) % 1000000007;
        first = second;
        second = cur;
    }
    return second;
};

斐波那契数列解析

Javascript

var fib = function (n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
};

递归可以理解成递归一颗二叉树，存在大量重叠子问题的重复计算借助备忘录，优化重叠子问题

Javascript

/**
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
    if (n < 2) return n;
    const map = new Map();
    return helper(n);

    function helper(n) {
        if (n < 2) return n;
        if (!map.has(n)) {
            map.set(n, helper(n - 1) + helper(n - 2));
        }
        return map.get(n);
    }
};

减少了重叠子问题，相当于把二叉树修剪成了左子节点都为空的二叉树，递归从大到小叠加 fib(n) + fib(n-1) + ... + fib(0)

换成迭代方式遍历，即可从 fib(0) + fib(1) + ... + fib(n) 备忘录换成 dp 表

如果需要频繁的求解 fib(n)，可以把 dp 表缓存到函数外

Javascript

/**
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
    if (n < 2) return n;
    let dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[i];
};

分析以上 dp 表空间复杂度 O(n) 可以优化到 O(1)

Javascript

var fib = function (n) {
    if (n < 2) return n;

    let first = 0,
        second = 1;
    for (let i = 2; i <= n; i++) {
        let cur = first + second;
        first = second;
        second = cur;
    }
    return second;
};

剑指 Offer II 093. 最长斐波那契数列

搞了好几个小时，实在是想不明白，先放放，后面再看

Javascript

/**
 * @param {number[]} arr
 * @return {number}
 */
function lenLongestFibSubseq(arr) {
    const len = arr.length;
    const map = new Map();
    for (let i = 0; i < len; i++) {
        map.set(arr[i], i);
    }
    const dp = new Array(len).fill(0).map(() => new Array(len).fill(0));
    let ans = 0;
    for (let i = 0; i < len; i++) {
        //
        for (let j = len - 1; j >= 0; j--) {
            //
            if (arr[j] * 2 <= arr[i]) {
                break;
            }
            if (map.has(arr[i] - arr[j])) {
                const k = map.get(arr[i] - arr[j]);
                dp[j][i] = Math.max(dp[k][j] + 1, 3);
                ans = Math.max(dp[j][i], ans);
            }
        }
    }
    return ans;
}

873. 最长的斐波那契子序列的长度

迭代暴力求解

Javascript

/**
 * @param {number[]} arr
 * @return {number}
 */
function lenLongestFibSubseq(arr) {
    const len = arr.length;
    const map = new Map();
    for (let i = 0; i < len; i++) {
        map.set(arr[i], i);
    }
    let ans = 0;
    // const dp = new Array(len).fill(0).map(() => new Array(len).fill(0));

    for (let i = 0; i < len; i++) {
        for (let j = i + 1; j < len; j++) {
            // dp[i][j]
            // dp[i][j] = 'x';
            let first = arr[i],
                second = arr[j],
                count = 0;
            while (map.has(first + second)) {
                const temp = first + second;
                // const k = map.get(temp);
                count = count > 0 ? count + 1 : 3;
                first = second;
                second = temp;
            }
            ans = Math.max(ans, count);
        }
    }
    // console.table(dp);
    return ans;
}

while 循环里面最差的时候复杂度为 O(n),平均时间复杂度为 O(n^2)，最坏时间复杂度为 O(n^3)

分析上述代码迭代过程，while 循环存在重复计算以 j,k 结尾的子问题的情况，可以使用 dp 表来优化时间复杂度

加上 dp 表解决重复子问题

Javascript

/**
 * @param {number[]} arr
 * @return {number}
 */
function lenLongestFibSubseq(arr) {
    const len = arr.length;
    const map = new Map();
    for (let i = 0; i < len; i++) {
        map.set(arr[i], i);
    }
    let ans = 0;
    // 定义dp表 dp[j][k] 为以 j,k 结尾的数列长度

    const dp = new Array(len).fill(0).map(() => new Array(len).fill(0));
    for (let i = 0; i < len; i++) {
        for (let j = i + 1; j < len; j++) {
            let first = arr[i],
                second = arr[j],
                count = 0;

            while (map.has(first + second)) {
                const temp = first + second;
                const k = map.get(temp);
                if (dp[map.get(second)][k] !== 0) {
                    count = dp[map.get(second)][k];
                    console.log('xxxx');
                    break;
                }
                count = count > 0 ? count + 1 : 3;
                // dp[j][k] = count;
                dp[map.get(second)][k] = count;
                console.table(dp);

                first = second;
                second = temp;
            }
            ans = Math.max(ans, count);
        }
    }
    // console.table(dp);
    return ans;
}

进一步思考 🤔，上述用的是自顶向下的方式去查找后一个元素 k，导致以 dp[j][k] 结尾的存在重复查找。如果改成自底向上（动态规划）则可以不需要重复计算

Javascript

/**
 * @param {number[]} arr
 * @return {number}
 */
function lenLongestFibSubseq(arr) {
    const len = arr.length;
    const map = new Map();
    for (let i = 0; i < len; i++) {
        map.set(arr[i], i);
    }
    let ans = 0;
    // 定义dp表 dp[i][j] 为以 i,j 结尾的数列长度
    const dp = new Array(len).fill(0).map(() => new Array(len).fill(0));
    for (let i = 0; i < len; i++) {
        for (let j = i + 1; j < len; j++) {
            const k = map.get(arr[j] - arr[i]);
            if (k !== undefined && k < i) {
                // 最少3个元素
                dp[i][j] = Math.max(dp[k][i] + 1, 3);
                ans = Math.max(ans, dp[i][j]);
            }
        }
    }
    // console.table(dp);
    return ans;
}

进一步思考 🤔 const k = map.get(arr[j] - arr[i]); 找的是已经遍历过的元素，定义 map 可以不需要单独遍历一遍。

时间复杂度 O(n^2) 空间复杂度 O(n

Javascript

/**
 * @param {number[]} arr
 * @return {number}
 */
function lenLongestFibSubseq(arr) {
    const len = arr.length;
    const map = new Map();
    let ans = 0;
    // 定义dp表 dp[i][j] 为以 i,j 结尾的数列长度
    const dp = new Array(len).fill(0).map(() => new Array(len).fill(0));
    for (let i = 0; i < len; i++) {
        map.set(arr[i], i);
        for (let j = i + 1; j < len; j++) {
            map.set(arr[i], i);
            const k = map.get(arr[j] - arr[i]);
            if (k !== undefined && k < i) {
                // 最少3个元素
                dp[i][j] = Math.max(dp[k][i] + 1, 3);
                ans = Math.max(ans, dp[i][j]);
            }
        }
    }
    // console.table(dp);
    return ans;
}

5. 最长回文子串

暴力穷举

暴力穷举所有的字串，并且判断该字串是否是回文

时间复杂度 O(n^3)

Javascript

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    const len = s.length;
    let maxLen = 0,
        result = '';
    for (let i = 0; i < len; i++) {
        for (let j = i + 1; j <= len; j++) {
            let subStr = s.substring(i, j);
            if (isPalindrome(subStr) && subStr.length > maxLen) {
                maxLen = subStr.length;
                result = subStr;
            }
        }
    }
    return result;
};

function isPalindrome(s) {
    const len = s.length;
    const half = (len / 2) >> 0;
    for (let i = 0; i < half; i++) {
        if (s[i] !== s[len - 1 - i]) {
            return false;
        }
    }
    return true;
}

动态规划

穷举所有字串的过程中，判断是否是回文的地方，存在重复计算，借助备忘录或者 dp table 来消除重复子问题的计算

时间复杂度 O(n^2) 空间复杂度 O(n^2)

Javascript

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    const len = s.length;
    let maxLen = 1,
        start = 0;

    const dp = Array.from({ length: len }, () => new Array(len).fill(false));
    // // 初始化对角线
    // for (let i = 0; i < len; i++) {
    //   dp[i][i] = true;
    // }

    for (let j = 1; j < len; j++) {
        dp[j][j] = true;
        for (let i = 0; i < j; i++) {
            dp[i][i] = true;
            // console.log('i,j', i, j);
            if (s[i] !== s[j]) {
                dp[i][j] = false;
            } else {
                // aba，aa 这种情况下 判断 首尾相等即可
                if (j - i < 3) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }

            //更新 ans
            if (dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1;
                start = i;
            }
        }
    }
    // console.table(dp);
    return s.substring(start, start + maxLen);
};

中心扩展解法

从 index=1 开始，以当前 index 为中心去找，左右 2 边满足条件的回文

时间复杂度 O(n^2) 空间复杂度 O(1)

Javascript

var longestPalindrome = function (s) {
    const len = s.length;
    //边界值
    if (len <= 1) return s;

    let i = 1;
    let maxStr = '';

    while (i <= len - 1) {
        let left = i - 1;
        let right = i + 1;

        // 2个回文的情况
        while (s[left] === s[i]) {
            left--;
        }

        // 2个回文的情况
        while (s[right] === s[i]) {
            right++;
        }
        // 基数个回文
        while (s[left] === s[right] && left >= 0 && right <= len - 1) {
            left--;
            right++;
        }
        console.log(i, left, right, s.slice(left + 1, right));
        const newStr = s.slice(left + 1, right);

        if (newStr.length > maxStr.length) {
            maxStr = newStr;
        }
        i++;
    }
    return maxStr;
};

322. 零钱兑换

暴力解法

对于每个硬币，可以选择使用或不使用，然后在下一次递归时处理剩余金额和剩余硬币。对所有硬币组合进行递归枚举，找到最少的硬币个数。

Javascript

function coinChange(coins, amount) {
    if (amount === 0) return 0;
    let min = Number.MAX_VALUE;
    for (let i = 0; i < coins.length; i++) {
        if (amount - coins[i] >= 0) {
            const res = coinChange(coins, amount - coins[i]);
            if (res !== -1) {
                min = Math.min(min, res + 1);
            }
        }
    }
    return min === Number.MAX_VALUE ? -1 : min;
}

述解法中存在的重复子问题是在计算每个目标金额的最小数量时，重复地计算了之前已经计算过的目标金额。例如，当计算目标金额为 11 时，需要计算目标金额为 10 和 9 的最小数量，而计算目标金额为 10 时又需要计算目标金额为 9 和 8 的最小数量，这导致了重复的计算。

通过 memoization 备忘录优化

Javascript

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
    // 使用数组来保存每个目标金额的最小数量
    const memo = new Array(amount + 1).fill(-1);
    // 定义递归函数
    function dfs(n) {
        // 如果目标金额为 0，返回 0
        if (n === 0) {
            return 0;
        }
        // 如果已经计算过目标金额 n 的最小数量，则直接返回
        if (memo[n] !== -1) {
            return memo[n];
        }
        let res = Infinity;
        // 遍历所有硬币面额
        for (let coin of coins) {
            // 如果硬币面额大于目标金额，则跳过
            if (n < coin) {
                continue;
            }
            // 计算使用当前硬币面额时的最小数量
            const subproblem = dfs(n - coin);
            // 如果子问题无解，则跳过
            if (subproblem === -1) {
                continue;
            }
            // 计算总数量，并更新最小数量
            res = Math.min(res, subproblem + 1);
        }
        // 如果存在可行解，则保存最小数量；否则，保存为 -1
        memo[n] = res === Infinity ? -1 : res;
        return memo[n];
    }
    // 调用递归函数，并返回结果
    return dfs(amount);
};

至此，该解法根动态规划基本已经一致，只不过动态规划是自底向上

动态规划

Javascript

function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
        for (const coin of coins) {
            if (i - coin >= 0) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
}

518. 零钱兑换 II

背包问题类型，定义dp[i][j]为在前 i 中 coins 选择 j 大小的面额时有多少种选择。

Javascript

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function (amount, coins) {
    // 定义dp[i]为有多少种 方式找到
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1;

    for (let coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    console.table(dp);
    return dp[amount];
};

300. 最长递增子序列

动态规划

时间复杂度 O(n^2) 空间复杂度 O(n)

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
    const len = nums.length;
    let ans = 1;
    const dp = new Array(len).fill(1);

    for (let i = 1; i < len; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
                ans = Math.max(ans, dp[i]);
            }
        }
    }
    return ans;
};

354. 俄罗斯套娃信封问题

相当于二维的最长递增子序列，可以先对二维数组按照 w 或者 h 升序排序，如果其中 2 个值相等的话，另外一个降序排列。一定要保证按照 w 升序排列后，h 降序排列，不然可能出现 [5,4]

Javascript

/**
 * @param {number[][]} envelopes
 * @return {number}
 */
var maxEnvelopes = function (envelopes) {
    let len = envelopes.length;
    // 按照宽度排序
    envelopes.sort((a, b) => (a[0] - b[0] === 0 ? b[1] - a[1] : a[0] - b[0]));

    // 最长递增子序列
    const dp = new Array(len).fill(1);
    let ans = 1;
    for (let i = 1; i < len; i++) {
        for (let j = 0; j < i; j++) {
            if (envelopes[j][1] < envelopes[i][1]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        ans = Math.max(ans, dp[i]);
    }
    return ans;
};

53. 最大子数组和

暴力解法

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    const len = nums.length;
    if (len === 1) return nums[0];
    let ans = -Infinity;
    for (let i = 0; i < len; i++) {
        let sum = 0;
        for (let j = i; j < len; j++) {
            sum += nums[j];
            ans = Math.max(ans, sum);
        }
    }
    return ans;
};

动态规划

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    const len = nums.length;
    if (len === 1) return nums[0];
    const dp = new Array(len).fill(-10e5);
    dp[0] = nums[0];
    let ans = Math.max(dp[0], -Infinity);
    for (let i = 1; i < len; i++) {
        dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
        ans = Math.max(ans, dp[i]);
    }
    return ans;
};

状态压缩一下

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    const len = nums.length;
    if (len === 1) return nums[0];
    let prev = nums[0];
    let ans = Math.max(prev, -Infinity);
    for (let i = 1; i < len; i++) {
        let cur = Math.max(nums[i], prev + nums[i]);
        ans = Math.max(ans, cur);
        prev = cur;
    }
    return ans;
    [];
};

1143. 最长公共子序列

暴力解法

定义 dp[i][j]为 s1[0..i-1] s2[0..j-1] 的 LCS 为 dp[i][j]

Javascript

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
    const len1 = text1.length,
        len2 = text2.length;
    return dp(len1 - 1, len2 - 1);

    function dp(i, j) {
        if (i === -1 || j === -1) {
            return 0;
        }
        if (text1[i] === text2[j]) {
            return dp(i - 1, j - 1) + 1;
        }
        return Math.max(dp(i - 1, j), dp(i, j - 1));
    }
};

动态规划

通过 dp 表，解决重复子问题

Javascript

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
    const len1 = text1.length,
        len2 = text2.length,
        dp = Array.from({ length: len1 + 1 }, () => new Array(len2 + 1).fill(0));
    for (let i = 1; i <= len1; i++) {
        for (let j = 1; j <= len2; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[len1][len2];
};

状态压缩，优化空间复杂度 ????? 可以使用滚动数组的方式来优化空间复杂度，将 dp 数组改为一个一维数组，每次遍历只记录当前行和上一行的值即可。以下是代码实现：

Javascript

var longestCommonSubsequence = function (text1, text2) {
    const len1 = text1.length,
        len2 = text2.length,
        dp = new Array(len2 + 1).fill(0);
    for (let i = 1; i <= len1; i++) {
        let pre = 0;
        for (let j = 1; j <= len2; j++) {
            const temp = dp[j];
            if (text1[i - 1] === text2[j - 1]) {
                dp[j] = pre + 1;
            } else {
                dp[j] = Math.max(dp[j - 1], dp[j]);
            }
            pre = temp;
        }
    }
    return dp[len2];
};

72. 编辑距离

暴力解法

自顶向下

Javascript

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
    const len1 = word1.length,
        len2 = word2.length;
    return dp(len1 - 1, len2 - 1);

    function dp(i, j) {
        if (i === -1) return j + 1;
        if (j === -1) return i + 1;
        if (word1[i] === word2[j]) {
            // 相同，则直接判断下一位
            return dp(i - 1, j - 1);
        } else {
            return Math.min(dp(i - 1, j) + 1, dp(i, j - 1) + 1, dp(i - 1, j - 1) + 1);
        }
    }
};

用备忘录解决重复子问题

Javascript

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
    const len1 = word1.length,
        len2 = word2.length;
    const map = new Map();
    return dp(len1 - 1, len2 - 1);

    function dp(i, j) {
        if (map.has(`${i}${j}`)) {
            return map.get(`${i}${j}`);
        }
        if (i === -1) return j + 1;
        if (j === -1) return i + 1;
        if (word1[i] === word2[j]) {
            // 相同，则直接判断下一位
            // return dp(i - 1, j - 1);
            map.set(`${i}${j}`, dp(i - 1, j - 1));
        } else {
            map.set(`${i}${j}`, Math.min(dp(i - 1, j) + 1, dp(i, j - 1) + 1, dp(i - 1, j - 1) + 1));
        }
        return map.get(`${i}${j}`);
    }
};

动态规划

自底向上

Javascript

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
    const len1 = word1.length,
        len2 = word2.length;

    // 定义dp[i][j] 为 0..i-1 , 0..j-1 的字符串的最小编辑距离
    const dp = Array.from({ length: len1 + 1 }, () => new Array(len2 + 1).fill(0));
    for (let i = 0; i <= len1; i++) {
        dp[i][0] = i;
    }
    for (let j = 0; j <= len2; j++) {
        dp[0][j] = j;
    }
    //
    for (let i = 1; i <= len1; i++) {
        for (let j = 1; j <= len2; j++) {
            //
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
            }
        }
    }
    return dp[len1][len2];
};

优化一下空间复杂度

Javascript

var minDistance = function (word1, word2) {
    const len1 = word1.length,
        len2 = word2.length;

    // 定义dp[j] 为 0..i-1 , 0..j-1 的字符串的最小编辑距离
    const dp = new Array(len2 + 1).fill(0);
    for (let j = 0; j <= len2; j++) {
        dp[j] = j;
    }
    //
    for (let i = 1; i <= len1; i++) {
        let prev = dp[0];
        dp[0] = i;
        for (let j = 1; j <= len2; j++) {
            const temp = dp[j];
            if (word1[i - 1] === word2[j - 1]) {
                dp[j] = prev;
            } else {
                dp[j] = Math.min(dp[j - 1], dp[j], prev) + 1;
            }
            prev = temp;
        }
    }
    return dp[len2];
};

516. 最长回文子序列

暴力解法

Javascript

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function (s) {
    return dp(0, s.length - 1);

    function dp(i, j) {
        if (i > j) {
            return 0;
        }
        if (i == j) {
            return 1;
        }
        if (s[i] === s[j]) {
            return dp(i + 1, j - 1) + 2;
        } else {
            return Math.max(dp(i + 1, j), dp(i, j - 1));
        }
    }
};

动态规划

Javascript

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function (s) {
    // 定义dp[i][j] 为 s[i..j] 的最长回文长度 为dp[i][j]
    const len = s.length,
        dp = Array.from({ length: len }, () => new Array(len).fill(0));
    for (let i = 0; i < len; i++) {
        // dp 表对角线 都是1
        dp[i][i] = 1;
    }

    // 需要斜着遍历
    for (let l = 1; l < len; l++) {
        //
        for (let i = 0; i < len - l; i++) {
            let j = i + l;
            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
            //
        }
    }
    // console.table(dp);
    return dp[0][len - 1];
};

状态压缩

状态压缩需要反着遍历，斜向遍历会导致值被覆盖了

Javascript

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function (s) {
    // 定义dp[i][j] 为 s[i..j] 的最长回文长度 为dp[i][j]
    const len = s.length,
        dp = new Array(len).fill(1);

    // 需要斜着遍历
    for (let i = len - 2; i >= 0; i--) {
        let pre = 0;
        for (let j = i + 1; j < len; j++) {
            // 初始值 为 0
            const temp = dp[j];
            if (s[i] === s[j]) {
                dp[j] = pre + 2;
            } else {
                dp[j] = Math.max(dp[j], dp[j - 1]);
            }
            pre = temp;
        }
    }
    //   console.table(dp);
    return dp[len - 1];
};

1312. 让字符串成为回文串的最少插入次数

暴力解法

Javascript

/**
 * @param {string} s
 * @return {number}
 */
var minInsertions = function (s) {
    return dp(0, s.length - 1);
    function dp(i, j) {
        if (i === j || i > j) {
            return 0;
        }
        if (s[i] === s[j]) {
            return dp(i + 1, j - 1);
        }
        return Math.min(dp(i + 1, j) + 1, dp(i, j - 1) + 1);
    }
};

可以用 dp 表或者备忘录解决重复子问题

动态规划

Javascript

/**
 * @param {string} s
 * @return {number}
 */
var minInsertions = function (s) {
    const len = s.length,
        dp = Array.from({ length: len }, () => new Array(len).fill(0));
    // 定义dp[i][j] 为s[i][j] 变成回文需要插入的最少次数

    for (let l = 1; l < len; l++) {
        for (let i = 0; i < len - l; i++) {
            const j = i + l;
            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
            }
        }
    }
    return dp[0][len - 1];
};

状态压缩（需要反着遍历才行）

Javascript

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function (s) {
    // 定义dp[i][j] 为 s[i..j] 的最长回文长度 为dp[i][j]
    const len = s.length,
        dp = new Array(len).fill(1);

    // 需要斜着遍历
    for (let i = len - 2; i >= 0; i--) {
        let pre = 0;
        for (let j = i + 1; j < len; j++) {
            // 初始值 为 0
            const temp = dp[j];
            if (s[i] === s[j]) {
                dp[j] = pre + 2;
            } else {
                dp[j] = Math.max(dp[j], dp[j - 1]);
            }
            pre = temp;
        }
    }
    //   console.table(dp);
    return dp[len - 1];
};

/**
 * @param {number} k
 * @param {number} n
 * @return {number}
 */
var superEggDrop = function (k, n) {
    return dp(k, n);
    function dp(k, n) {
        if (k === 1) return n;
        if (n === 0) return 0;
        let res = Infinity;
        for (let i = 1; i <= n; i++) {
            res = Math.min(res, Math.max(dp(k - 1, n - 1), dp(k, n - i)) + 1);
        }
        return res;
    }
};

备忘录优化一下重叠子问题

Javascript

/**
 * @param {number} k
 * @param {number} n
 * @return {number}
 */
var superEggDrop = function (k, n) {
    let map = new Map();
    return dp(k, n);
    function dp(k, n) {
        if (k === 1) return n;
        if (n === 0) return 0;
        if (map.has(`${k}${n}`)) {
            return map.get(`${k}${n}`);
        }
        let res = Infinity;
        for (let i = 1; i <= n; i++) {
            res = Math.min(res, Math.max(dp(k - 1, n - 1), dp(k, n - i)) + 1);
        }
        map.set(`${k}${n}`, res);
        return res;
    }
};

二分搜索优化

todo：

312. 戳气球

暴力解法

时间复杂度 O(n^3) n 为 nums 长度

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxCoins = function (nums) {
    return dp(nums);

    function dp(nums) {
        const len = nums.length;
        if (len === 0) return 1;
        if (len === 1) return nums[0];
        let ans = 0;
        for (let k = 0; k < len; k++) {
            ans = Math.max(ans, (nums[k - 1] || 1) * nums[k] * (nums[k + 1] || 1) + dp(nums.slice(0, k).concat(nums.slice(k + 1))));
        }
        return ans;
    }
};
console.log(maxCoins([3, 1, 5, 8]));

动态规划

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxCoins = function (nums) {
    const len = nums.length,
        dp = Array.from({ length: len + 2 }, () => new Array(len + 2).fill(0));
    const points = new Array(len + 2);
    points[0] = 1;
    points[len + 1] = 1;
    for (let i = 1; i <= len; i++) {
        points[i] = nums[i - 1];
    }

    for (let i = len; i >= 0; i--) {
        for (let j = i + 1; j < len + 2; j++) {
            for (let k = i + 1; k < j; k++) {
                dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + points[i] * points[j] * points[k]);
            }
        }
    }
    return dp[0][len + 1];
};

1000. 合并石头的最低成本

回溯算法

时间复杂度 O((n/K)^n) 空间复杂度 O(n) 超时了

Javascript

/**
 * @param {number[]} stones
 * @param {number} K
 * @return {number}
 */

var mergeStones = function (stones, K) {
    const n = stones.length;
    if ((n - 1) % (K - 1) !== 0) {
        return -1;
    }

    let minCost = Number.MAX_SAFE_INTEGER;
    backtrack(0, stones);
    return minCost;

    function backtrack(acc, arr) {
        if (arr.length === 1) {
            // console.log('acc', acc);
            minCost = Math.min(minCost, acc);

            return;
        }
        if (arr.length < K) {
            return;
        }
        const n = arr.length;
        for (let i = 0; i <= n - K; i++) {
            const sum = arr.slice(i, i + K).reduce((acc, cur) => acc + cur, 0);
            const newArr = arr.slice(0, i).concat(sum, arr.slice(i + K));
            // console.log(acc, newArr);
            backtrack(acc + sum, newArr);
        }
    }
};

记忆化处理还是超时了

时间复杂度 O(n^3)空间复杂度 O(n)

Javascript

/**
 * @param {number[]} stones
 * @param {number} K
 * @return {number}
 */
var mergeStones = function (stones, K) {
    const n = stones.length;
    if ((n - 1) % (K - 1) !== 0) {
        return -1;
    }

    let minCost = Number.MAX_SAFE_INTEGER;
    const memo = new Map(); // memoization cache
    backtrack(0, stones);

    return minCost;

    function backtrack(acc, arr) {
        if (arr.length === 1) {
            minCost = Math.min(minCost, acc);
            return;
        }

        const key = `${arr.join(',')}:${acc}`; // generate unique key for memoization
        if (memo.has(key)) {
            // memoization check
            minCost = Math.min(minCost, memo.get(key));
            return;
        }

        if (arr.length < K) {
            return;
        }

        const n = arr.length;
        for (let i = 0; i <= n - K; i++) {
            const sum = arr.slice(i, i + K).reduce((acc, cur) => acc + cur, 0);
            const newArr = arr.slice(0, i).concat(sum, arr.slice(i + K));
            backtrack(acc + sum, newArr);
        }

        memo.set(key, minCost); // memoize the result
    }
};

function pack(w, n, wt, val) {
    // dp[i][j] 表示对于前 i 个物品，限重 j 最大能装 dp[i][j]
    const dp = Array.from({ length: n + 1 }, () => new Array(w + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= w; j++) {
            // 装满了，放不上了
            if (j - wt[i - 1] < 0) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j - wt[i - 1]] + val[i - 1], dp[i - 1][j]);
            }
        }
    }
    return dp[n][w];
}

121. 买卖股票的最佳时机

best-time-to-buy-and-sell-stock

分析：题目意思，只能买一次，卖出一次，那就是寻找单调递增的最大间隔值。

Javascript

/*
 * 121. 买卖股票的最佳时机
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    const len = prices.length;
    let i = 0;
    let minPrice = Infinity;
    let ans = 0;
    while (i < len) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else {
            ans = Math.max(ans, prices[i] - minPrice);
        }
        i++;
    }
    return ans;
};

122. 买卖股票的最佳时机 II

Javascript

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    const n = prices.length;
    const dp = Array.from({ length: n }, () => new Array(2).fill(0));
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }
    return dp[n - 1][0];
};

状态压缩

Javascript

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    const n = prices.length;
    let dp0 = 0,
        dp1 = -prices[0];

    for (let i = 1; i < n; i++) {
        let newDp0 = Math.max(dp0, dp1 + prices[i]);
        let newDp1 = Math.max(dp1, dp0 - prices[i]);
        dp0 = newDp0;
        dp1 = newDp1;
    }
    return dp0;
};

贪心算法

var maxProfit = function (prices) {
    let maxProfit = 0;
    for (let i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            maxProfit += prices[i] - prices[i - 1];
        }
    }
    return maxProfit;
};

123. 买卖股票的最佳时机 III

Javascript

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    const n = prices.length;
    let buy1 = -prices[0],
        buy2 = -prices[0];
    let sell1 = 0,
        sell2 = 0;
    for (let i = 1; i < n; i++) {
        buy1 = Math.max(buy1, -prices[i]);
        sell1 = Math.max(sell1, buy1 + prices[i]);
        // 重点，需要把 sell1 的利润 转移到 buy2 上,相当于用 sell1 的利润抵扣 buy2 的买入价格
        buy2 = Math.max(buy2, sell1 - prices[i]);
        sell2 = Math.max(sell2, buy2 + prices[i]);
    }
    return sell2;
};

剑指 Offer 62. 圆圈中最后剩下的数字

数学

Javascript

var lastRemaining = function (n, m) {
    let pos = 0;
    for (let i = 2; i <= n; i++) {
        pos = (pos + m) % i;
    }
    return pos;
};

Javascript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function (nums, target) {
    let ans = 0;
    backtrack(0, 0);
    return ans;

    function backtrack(sum, index) {
        if (nums.length === index) {
            if (sum === target) {
                ans++;
            }
            return;
        }

        backtrack(sum + nums[index], index + 1);

        backtrack(sum - nums[index], index + 1);
    }
};

分析其中的重叠子问题，假设 nums[index] ===0 的时候，这个时候就会发现，存在重复计算。只要存在一次重复计算，必然会存在多次重复计算

消除重叠子问题

通过备忘录或者 dp 表去解决重叠子问题

Javascript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function (nums, target) {
    let map = new Map();

    let ans = backtrack(0, 0);
    console.log([...map.entries()]);
    return ans;

    function backtrack(sum, index) {
        if (nums.length === index) {
            if (sum === target) {
                return 1;
            }
            return 0;
        }
        const key = `${sum}${index}`;
        if (map.has(key)) {
            return map.get(key);
        }
        let result = backtrack(sum + nums[index], index + 1) + backtrack(sum - nums[index], index + 1);
        map.set(key, result);
        return result;
    }
};

console.log(findTargetSumWays([1, 1, 1, 1, 1], 3));

function count(n) {
    let ans = 0;
    backtrack(0);
    return ans;

    function backtrack(i) {
        if (i > n) return;
        if (i === n) {
            ans++;
            return;
        }
        backtrack(i + 1);
        backtrack(i + 2);
    }
}

暴力穷举。相当于遍历一颗 2 叉树。时间复杂度 O(n) 空间复杂

Javascript

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
    let map = new Map();
    return backtrack(0);

    function backtrack(i) {
        if (i > n) return 0;
        if (i === n) {
            return 1;
        }
        if (map.has(i)) {
            return map.get(i);
        }
        let sum = backtrack(i + 1) + backtrack(i + 2);
        map.set(i, sum);
        return sum;
    }
};

动态规划

定义 dp 表，当前状态可以通过前 2 个状态计算出来

时间复杂度 O(n) 空间复杂度 O(n)

Javascript

function climbStairs(n) {
    if (n == 1) return 1;
    const dp = new Array(n + 1).fill(0);
    dp[1] = 1;
    dp[2] = 2;

    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

优化空间复杂度。通过以上代码可以发现，只有 dp[i-1] dp[i-2] 2 个值需要保存。

时间复杂度 O(n) 空间复杂度 O(1)

Javascript

function climbStairs(n) {
    if (n == 1) return 1;
    let first = 1,
        second = 2,
        cur = 0;

    for (let i = 3; i <= n; i++) {
        cur = first + second;
        first = second;
        second = cur;
    }
    return second;
}

1092. 最短公共超序列

动态规划

找到最短公共超序列的长度通过超序列长度构造超序列

Javascript

function shortestCommonSupersequence(str1, str2) {
    const m = str1.length,
        n = str2.length;

    // dp[i][j] 表示字符串 s1[0...i-1] 和字符串 s2[0...j-1] 的最短公共超序列长度
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

    // 初始化边界
    for (let i = 1; i <= m; i++) {
        dp[i][0] = i;
    }
    for (let j = 1; j <= n; j++) {
        dp[0][j] = j;
    }

    // 动态规划
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (str1[i - 1] === str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
            }
        }
    }

    // 构造最短公共超序列
    let i = m,
        j = n,
        k = dp[m][n];
    const res = new Array(k);

    while (i > 0 && j > 0) {
        if (str1[i - 1] === str2[j - 1]) {
            res[--k] = str1[i - 1];
            i--;
            j--;
            // 选择超序列短的
        } else if (dp[i - 1][j] < dp[i][j - 1]) {
            res[--k] = str1[i - 1];
            i--;
        } else {
            res[--k] = str2[j - 1];
            j--;
        }
    }
    while (i > 0) {
        res[--k] = str1[--i];
    }
    while (j > 0) {
        res[--k] = str2[--j];
    }

    return res.join('');
}

Rust

let m = str1.len();
  let n = str2.len();

  let mut dp = [[0; 1001]; 1001];
  for i in 1..=m {
      dp[i][0] = i;
  }
  for j in 1..=n {
      dp[0][j] = j;
  }

  for i in 1..=m {
      for j in 1..=n {
          dp[i][j] = if str1.as_bytes()[i - 1] == str2.as_bytes()[j - 1] {
              dp[i - 1][j - 1] + 1
          } else {
              std::cmp::min(dp[i - 1][j], dp[i][j - 1]) + 1
          };
      }
  }

  let mut res = Vec::with_capacity(dp[m][n]);
  let (mut i, mut j) = (m, n);

  while i > 0 && j > 0 {
      if str1.as_bytes()[i - 1] == str2.as_bytes()[j - 1] {
          res.push(str1.as_bytes()[i - 1]);
          i -= 1;
          j -= 1;
      } else if dp[i - 1][j] < dp[i][j - 1] {
          res.push(str1.as_bytes()[i - 1]);
          i -= 1;
      } else {
          res.push(str2.as_bytes()[j - 1]);
          j -= 1;
      }
  }

  while i > 0 {
      res.push(str1.as_bytes()[i - 1]);
      i -= 1;
  }

  while j > 0 {
      res.push(str2.as_bytes()[j - 1]);
      j -= 1;
  }

  res.reverse();
  String::from_utf8(res).unwrap()

1641. 统计字典序元音字符串的数目

回溯算法

暴力求解，时间复杂度 O(5^n) 空间复杂度 O(n)

Javascript

/**
 * @param {number} n
 * @return {number}
 */
var countVowelStrings = function (n) {
    let ans = 0,
        letters = ['a', 'e', 'i', 'o', 'u'];
    backtrack('', n);
    return ans;

    function backtrack(path, len) {
        if (path.length === n) {
            ans++;
        }

        if (len <= 0) {
            return;
        }

        for (let letter of letters) {
            if (path.length === 0 || letter.charCodeAt(0) >= path[path.length - 1].charCodeAt(0)) {
                backtrack(path + letter, len - 1);
            } else {
                backtrack(path, len - 1);
            }
        }
    }
};

动态规划

Javascript

/**
 * @param {number} n
 * @return {number}
 */
function countVowelStrings(n) {
    const dp = new Array(5).fill(1);
    for (let i = 1; i < n; i++) {
        for (let j = 1; j < 5; j++) {
            dp[j] += dp[j - 1];
        }
    }
    return dp.reduce((acc, item) => {
        acc += item;
        return acc;
    }, 0);
}

1039. 多边形三角剖分的最低得分

回溯算法

超时了，时间复杂度 O(n^3) 空间复杂度 O(n^3)

Javascript

/**
 * @param {number[]} values
 * @return {number}
 */
var minScoreTriangulation = function (values) {
    const n = values.length;
    let minScore = Number.MAX_SAFE_INTEGER;

    backtrack(0, [...Array(n).keys()]);
    return minScore;

    function backtrack(score, vertices) {
        if (vertices.length === 3) {
            minScore = Math.min(minScore, score + values[vertices[0]] * values[vertices[1]] * values[vertices[2]]);
            return;
        }
        for (let i = 1; i < vertices.length - 1; i++) {
            const left = vertices[i - 1];
            const right = vertices[i + 1];
            const newVertices = [...vertices.slice(0, i), ...vertices.slice(i + 1)];
            backtrack(score + values[left] * values[right] * values[vertices[i]], newVertices);
        }
    }
};

动态规划

时间复杂度 O(n^2) 空间复杂度 O(n^2)

Javascript

var minScoreTriangulation = function (values) {
    const n = values.length;
    const memo = new Map();
    return dp(0, n - 1);

    function dp(i, j) {
        if (i + 2 > j) {
            return 0;
        }
        if (i + 2 === j) {
            return values[i] * values[i + 1] * values[j];
        }
        const key = i * n + j;

        if (!memo.has(key)) {
            let minScore = Number.MAX_VALUE;
            for (let k = i + 1; k < j; k++) {
                minScore = Math.min(minScore, values[i] * values[k] * values[j] + dp(i, k) + dp(k, j));
            }
            memo.set(key, minScore);
        }
        return memo.get(key);
    }
};

1125. 最小的必要团队

回溯算法

时间复杂度 O(n _ 2^n _ m) 空间复杂度 O(n * 2^n)

Javascript

/**
 * @param {string[]} req_skills
 * @param {string[][]} people
 * @return {number[]}
 */
var smallestSufficientTeam = function (req_skills, people) {
    let ans = [];
    backtrack(new Set(), new Set());
    return ans;

    function backtrack(skillSet, peopleSet) {
        if (skillSet.size === req_skills.length) {
            if (ans.length === 0 || peopleSet.size < ans.length) {
                ans = [...peopleSet];
            }
            return;
        }
        for (let i = 0; i < people.length; i++) {
            if (!peopleSet.has(i)) {
                let set = new Set(skillSet);

                for (let skill of people[i]) {
                    set.add(skill);
                }
                let peopleNew = new Set(peopleSet);
                peopleNew.add(i);
                // console.log(set, peopleNew);
                backtrack(set, peopleNew);
            }
        }
    }
};

动态规划

Javascript

/**
 * @param {string[]} req_skills
 * @param {string[][]} people
 * @return {number[]}
 */
var smallestSufficientTeam = function (req_skills, people) {
    // Create a map to map skills to their indices
    const skillIndices = new Map();
    for (let i = 0; i < req_skills.length; i++) {
        skillIndices.set(req_skills[i], i);
    }

    // Create a binary representation for each person's skills
    const peopleSkills = new Array(people.length).fill(0);
    for (let i = 0; i < people.length; i++) {
        for (let j = 0; j < people[i].length; j++) {
            const skill = people[i][j];
            const index = skillIndices.get(skill);
            peopleSkills[i] |= 1 << index;
        }
    }

    // Initialize the state table
    const n = req_skills.length;
    const m = people.length;
    const dp = new Array(1 << n).fill(Infinity);
    dp[0] = 0;

    // Fill the state table using dynamic programming
    const path = new Array(1 << n);
    path[0] = [-1];
    for (let i = 0; i < m; i++) {
        const skillSet = peopleSkills[i];
        for (let j = (1 << n) - 1; j >= 0; j--) {
            const newSkillSet = j | skillSet;
            if (dp[newSkillSet] > dp[j] + 1) {
                dp[newSkillSet] = dp[j] + 1;
                path[newSkillSet] = path[j].concat(i);
            }
        }
    }

    // Return the result
    return path[(1 << n) - 1].slice(1);
};