不同路径、Longest Increasing Subsequence和单词拆分

不同路径
一个机器人位于一个 m x n 网格的左上角，机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角，问总共有多少条不同的路径？
示例 1
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2
输入: m = 7, n = 3
输出: 28
思路
A B C D
E F G H
从点 (x=0,y=0)(x = 0,y = 0)(x=0,y=0) 出发，每次只能向下或者向右移动一步，因此下一点的坐标为(x+1,y)(x + 1, y)(x+1,y) 或者(x,y+1)(x, y + 1)(x,y+1)，一直到(x=m,y=n)(x = m, y = n)(x=m,y=n)。在上图中，H 只能从 G 或者 D 达到，因此从 A 到 H 的路径数等于从 A 到 D 的路径与从 A 到 G 的路径之和。得出路径数量 T(m,n)=T(m−1,n)+T(m,n−1)T(m, n) = T(m-1, n) + T(m, n-1)T(m,n)=T(m−1,n)+T(m,n−1)。
我们又发现，当$m = 1$ 或 $n = 1$ 时（只能一直往下或往右走），路径数量为1，这里得出跳出递归的条件。
方法一   递归
详解
由上面的分析可得，到达(m,n) (m, n)(m,n)的路径数量为(m,n−1) (m, n-1)(m,n−1)坐标的路径数量与 (m−1,n)(m-1, n)(m−1,n)坐标的路径数量之和 。可以使用最简单粗暴的递归方法
代码
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
const uniquePaths = function (m, n) {
  if (m === 1 || n === 1) {
    return 1;
  }
  return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
};
方法二   动态规划
详解
根据以上思路，可以推出状态转移方程为
​dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i - 1][j] + dp[i][j - 1]dp[i][j]=dp[i−1][j]+dp[i][j−1]​
1
1
1
1
1
1
1
1
2
3
4
5
6
7
1
3
6
10
15
21
28
代码
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
const uniquePaths = function (m, n) {
  const dp = new Array(m);
  for (let i = 0; i < m; i++) {
    dp[i] = new Array(n);
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0 || j === 0) {
        dp[i][j] = 1;
      } else {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      }
    }
  }
  return dp[m - 1][n - 1];
};
复杂度分析
时间复杂度： O(m∗n)O(m * n)O(m∗n) 
上述解法中，对 mmm 和 nnn 进行了双重循环，时间复杂度跟数字的个数线性相关，即为 O(m∗n)O(m*n)O(m∗n) 
空间复杂度： O(m∗n)O(m * n)O(m∗n) 
申请了大小为 m∗nm * nm∗n的二维数组
方法三 动态规划优化
减少空间复杂度
详解
我们观察表格发现，下一个值等于当前值加上一行的值，利用这个发现，可以来压缩空间，用一维数组来实现
const uniquePaths = function (m, n) {
  const dp = new Array(n).fill(1);
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[j] = dp[j - 1] + dp[j];
    }
  }
  return dp[n - 1];
};
复杂度分析
时间复杂度： O(m∗n)O(m * n)O(m∗n) 
空间复杂度：O(n)O(n)O(n)​
方法四  排列组合
详解
其实这是个高中数学问题。因为机器人只能向右或者向下移动，那么不论有多少中路径，向右和向下走的步数都是一样的。当 m=3，n=2m = 3，n = 2 m=3，n=2 时，机器人向下走了一步，向右走了两步即可到达终点。所以我们可以得到
路径 = 从右边开始走的路径总数 + 从下边开始走的路径总数，转化为排列组合问题
不包括起点和终点，共移动 N=m+n−2N = m + n - 2N=m+n−2，向右移动K=m−1K = m - 1K=m−1，将 NNN 和 KKK 代入上述公式，可得
因此得出答案 Cm+n−2m−1C_{m + n -2}^{m - 1}Cm+n−2m−1​​
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
const uniquePaths = function (m, n) {
  const N = m + n - 2;
  const K = n - 1;
  let num = 1;
  for (let i = 1; i <= K; i++) {
    num = num * (N - K + i) / i;
  }
  return num;
};
复杂度分析
时间复杂度：O(n)O(n)O(n)​
空间复杂度：O(1)O(1)O(1)​
Longest Increasing Subsequence
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
方法一 动态规划
思路
状态定义：res[i] 表示以 nums[i] 为当前最长递增子序列尾元素的长度
转移方程：通过方程 res[i] = Math.max(res[i], nums[i] > nums[j] ? res[j] + 1 : 1)，动态计算出各上升子序列的长度。
倒序取值：res 数组进行倒序，第一个即为最大长度的值。
详解
如果给定数组长度小于等于 1，则最长上升子序列的长度等于数组长度。
初始化一个长度等于给定数组的长度，且元素都为 1 的数组 res。
当 nums[i] > nums[j] 时，nums[i] 可以作为前一个最长的递增子序列 res[j] 新的尾元素，而组成新的相对于 res[i] 能够拼接的更长的递增子序列 res[i] = res[j] + 1，因为新的 res[i] 能够拼接的最长长度取决于 nums[i] 这个新的尾元素，而这个 nums[i] 不一定大于 nums[j]，所以也不一定大于 res[j]，那么在 i ~ j 之间，最大的递增子序列为 Max(res[i], res[j]+1)；当 nums[i] <= nums[j]，长度为元素本身，即为 1。所以得出方程 res[i] = Math.max(res[i], nums[i] > nums[j] ? res[j] + 1 : 1)，通过转移方程收集
各上升子序列的长度。
通过 sort 函数对 res 倒序排列，第一元素值 res[0] 就是最长的上升子序列长度。
/**
 * @param {number[]} nums
 * @return {number}
 */
const lengthOfLIS = function (nums) {
  const len = nums.length;
  if (len <= 1) {
    return len;
  }
  // 初始化默认全为1
  const res = new Array(len).fill(1);
  for (let i = 1; i < len; i++) {
    for (let j = 0; j < i; j++) {
      // 转移方程
      res[i] = Math.max(res[i], nums[i] > nums[j] ? res[j] + 1 : 1);
    }
  }
  // 倒序
  res.sort((a, b) => b - a);
  return res[0];
};
复杂度分析
时间复杂度：O(n2)O(n^2)O(n2)​
空间复杂度：O(n)O(n)O(n)​
方法二 二分查找
思路
当前遍历元素大于前一个递增子序列的尾元素时（nums[i] > tail[end]），将当前元素追加到 tail 后面，这里解法其实和方法一中
nums[i] > nums[j] 的解法一样。
当 nums[i] <= tail[end] 时，寻找前一个递增子序列第一个大于当前值的元素，替换为当前值，查找用二分，最后左边的元素即为查找到的需要被替换的结果元素。
详解
1、如果给定数组长度小于等于 1，则最长上升子序列的长度等于数组长度。 2、初始化一个长度等于给定数组的长度，且第一个元素值等于给定数组的第一个元素值的数组 tail，tail 用来存储最长递增子序列的元素。 3、循环给定的数组，当前遍历元素大于前一个递增子序列的尾元素时（nums[i] > tail[end]），将当前元素追加到 tail 后面，这里解法 其实和方法一中nums[i] > nums[j] 的解法一样；当 nums[i] <= tail[end] 时，寻找前一个递增子序列第一个大于当前值的元素，替换为当前值，查找用二分，最后左边的元素即为查找到的需要被替换的结果元素。 4、循坏完之后，end + 1 即为最长的上升子序列长度。
/**
 * @param {number[]} nums
 * @return {number}
 */
const lengthOfLIS = function (nums) {
  const len = nums.length;
  if (len <= 1) {
    return len;
  }
  const tail = new Array(len);
  tail[0] = nums[0];
  let end = 0;
  for (let i = 1; i < len; i++) {
    if (nums[i] > tail[end]) {
      end += 1;
      tail[end] = nums[i];
    } else {
      let left = 0;
      let right = end;
      // 二分查找
      while (left < right) {
        // 位运算，右移一位
        const mid = left + ((right - left) >> 1);
        if (tail[mid] < nums[i]) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      tail[left] = nums[i];
    }
  }
  return end + 1;
};
复杂度分析
时间复杂度：O(nlogN)O(nlogN)O(nlogN)​
外层一个数组循环遍历，里面嵌套一个二分查找，所以是 O(nlogN)O(nlogN)O(nlogN)​
空间复杂度：O(n)O(n)O(n)​
创建的数组 tail 占用空间大小为 n，循环遍历中并没有分配新的空间
单词拆分
示例
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
注意你可以重复使用字典中的单词。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]  
输出: true  
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]  
输出: true  
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]  
输出: false
方法一 暴力破解法
思路
把字符串 s 的前缀从短到长拆出来进行判断是否在单词字典中，若在字典中则把前缀截取掉继续递归，直到字符串的长度为 0。在递归中若遇到字符串任何长度的前缀都无法匹配到字典中的单词，则回溯到上层递归。
详解
1、检查字典中是否有字符串的前缀；
2、若有的话，将字符串去掉这个前缀后继续遍历，重复步骤 1、2；
3、若某次调用发现整个字符串都已拆分并且都在字典内则返回 true；
const wordBreak = function (s, wordDict) {
  if (s.length === 0) {
    return true;
  }
  for (let i = 0; i < wordDict.length; i += 1) {
    const startIndex = s.indexOf(wordDict[i]);
    if (startIndex === 0) {
      // 将字符串去掉这个匹配到的前缀后继续遍历
      const temp = s.slice(startIndex + wordDict[i].length);
      if (wordBreak(temp, wordDict) === true) {
        return true;
      }
    }
  }
  return false;
};
时间复杂度：最坏情况下是 O(nn)O(n^n)O(nn)，因为考虑 s = 'aaaaaaaaaaaaaaaa'， wordDict = ['a']，每一个字符都在字典中，此时递归的时间复杂度会达到 O(nn) O(n^n) O(nn)，妥妥超时
空间复杂度：O(1)O(1)O(1)，循环中申请了 3 个临时变量，与输入的字符串的长度无关，空间占用属于常数阶，故空间复杂度为 O(1)O(1)O(1)。
方法二 动态规划
思路
dp[i] 表示字符串 s 从开始到 i 位置是否可以由 wordDict 组成。使用 j 从头开始遍历，若 dp[i] 可由 wordDict 组成，并且 i 到 j 之间的单词可以在 wordDict中找到，则说明 dp[i] = true。
详解
1、第一层遍历：用 i 从头到尾遍历字符串；
2、第二层遍历：用 j 从头到 i 遍历字符串；
3、若 dp[j] = true 而且字典中存在字符串 s[i~j]，则说明 dp[i] = true；
4、继续步骤 1、2，直到整个字符串都遍历一遍；
5、若 dp[s.length()] = true，则说明字符可由字段中的单词组合而成；
代码
const wordBreak = function (s, wordDict) {
  const len = s.length;
  const dp = new Array(len + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= len; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordDict.includes(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[len];
};
复杂度分析
时间复杂度：O(n2)O(n^2)O(n2)​
因为有两层循环，每层循环都从头遍历到尾。
空间复杂度：O(n)O(n)O(n)​
因为只开辟了一个 nnn长度的数组。
方法三 动态规划（优化版）
思路
第二层遍历中不用每次遍历 i 的长度，只要遍历字典中最长单词的长度 maxStep 即可。
详解
1、第一层遍历：用 i 从头到尾遍历字符串；
2、第二层遍历：用 j 从 i - maxStep 到 i 遍历字符串；
3、若 dp[j] = true 而且字典中存在字符串 s[i~j]，则说明 dp[i] = true；
4、继续步骤 1、2，直到整个字符串都遍历一遍；
5、若 dp[s.length()] = true，则说明字符可由字段中的单词组合而成；
const wordBreak = function (s, wordDict) {
  const len = s.length;
  const dp = new Array(len + 1).fill(false);
  dp[0] = true;
  // 计算单词的最长长度
  let maxStep = 0;
  for (let i = 0; i < wordDict.length; i++) {
    if (wordDict[i].length > maxStep) {
      maxStep = wordDict[i].length;
    }
  }
  for (let i = 1; i <= len; i++) {
    const startOfJ = i - maxStep > 0 ? i - maxStep : 0;
    for (let j = startOfJ; j < i; j++) {
      if (dp[j] && wordDict.includes(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[len];
};
复杂度分析
时间复杂度：O(n2)O(n^2)O(n2)​
因为有两层循环，每层循环都从头遍历到尾。
空间复杂度：O(n)O(n)O(n)​
因为最长只开辟了一个 nnn 长度的数组。