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

不同路径

一个机器人位于一个 m x n 网格的左上角,机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角,问总共有多少条不同的路径?
示例 1
1
输入: m = 3, n = 2
2
输出: 3
3
解释:
4
从左上角开始,总共有 3 条路径可以到达右下角。
5
1. 向右 -> 向右 -> 向下
6
2. 向右 -> 向下 -> 向右
7
3. 向下 -> 向右 -> 向右
Copied!
示例 2
1
输入: m = 7, n = 3
2
输出: 28
Copied!

思路

1
A B C D
2
E F G H
Copied!
从点
(x=0,y=0)(x = 0,y = 0)
出发,每次只能向下或者向右移动一步,因此下一点的坐标为
(x+1,y)(x + 1, y)
或者
(x,y+1)(x, y + 1)
,一直到
(x=m,y=n)(x = m, y = n)
。在上图中,H 只能从 G 或者 D 达到,因此从 A 到 H 的路径数等于从 A 到 D 的路径与从 A 到 G 的路径之和。得出路径数量
T(m,n)=T(m1,n)+T(m,n1)T(m, n) = T(m-1, n) + T(m, n-1)
我们又发现,当$m = 1$ 或 $n = 1$ 时(只能一直往下或往右走),路径数量为1,这里得出跳出递归的条件。

方法一 递归

详解
由上面的分析可得,到达
(m,n) (m, n)
的路径数量为
(m,n1) (m, n-1)
坐标的路径数量与
(m1,n)(m-1, n)
坐标的路径数量之和 。可以使用最简单粗暴的递归方法
代码
1
/**
2
* @param {number} m
3
* @param {number} n
4
* @return {number}
5
*/
6
const uniquePaths = function (m, n) {
7
if (m === 1 || n === 1) {
8
return 1;
9
}
10
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
11
};
Copied!

方法二 动态规划

详解
根据以上思路,可以推出状态转移方程为
dp[i][j]=dp[i1][j]+dp[i][j1]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
代码
1
/**
2
* @param {number} m
3
* @param {number} n
4
* @return {number}
5
*/
6
const uniquePaths = function (m, n) {
7
const dp = new Array(m);
8
for (let i = 0; i < m; i++) {
9
dp[i] = new Array(n);
10
}
11
for (let i = 0; i < m; i++) {
12
for (let j = 0; j < n; j++) {
13
if (i === 0 || j === 0) {
14
dp[i][j] = 1;
15
} else {
16
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
17
}
18
}
19
}
20
return dp[m - 1][n - 1];
21
};
Copied!
复杂度分析
  • 时间复杂度:
    O(mn)O(m * n)
上述解法中,对
mm
nn
进行了双重循环,时间复杂度跟数字的个数线性相关,即为
O(mn)O(m*n)
  • 空间复杂度:
    O(mn)O(m * n)
申请了大小为
mnm * n
的二维数组

方法三 动态规划优化

减少空间复杂度
详解
我们观察表格发现,下一个值等于当前值加上一行的值,利用这个发现,可以来压缩空间,用一维数组来实现
1
const uniquePaths = function (m, n) {
2
const dp = new Array(n).fill(1);
3
for (let i = 1; i < m; i++) {
4
for (let j = 1; j < n; j++) {
5
dp[j] = dp[j - 1] + dp[j];
6
}
7
}
8
return dp[n - 1];
9
};
Copied!
复杂度分析
  • 时间复杂度:
    O(mn)O(m * n)
  • 空间复杂度:
    O(n)O(n)

方法四 排列组合

详解
其实这是个高中数学问题。因为机器人只能向右或者向下移动,那么不论有多少中路径,向右和向下走的步数都是一样的。当
m=3n=2m = 3,n = 2
时,机器人向下走了一步,向右走了两步即可到达终点。所以我们可以得到
路径 = 从右边开始走的路径总数 + 从下边开始走的路径总数,转化为排列组合问题
不包括起点和终点,共移动
N=m+n2N = m + n - 2
,向右移动
K=m1K = m - 1
,将
NN
KK
代入上述公式,可得
因此得出答案
Cm+n2m1C_{m + n -2}^{m - 1}
1
/**
2
* @param {number} m
3
* @param {number} n
4
* @return {number}
5
*/
6
const uniquePaths = function (m, n) {
7
const N = m + n - 2;
8
const K = n - 1;
9
let num = 1;
10
for (let i = 1; i <= K; i++) {
11
num = num * (N - K + i) / i;
12
}
13
return num;
14
};
Copied!
复杂度分析
  • 时间复杂度:
    O(n)O(n)
  • 空间复杂度:
    O(1)O(1)

Longest Increasing Subsequence

给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例
1
输入: [10,9,2,5,3,7,101,18]
2
输出: 4
3
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
Copied!

方法一 动态规划

思路
  • 状态定义:res[i] 表示以 nums[i] 为当前最长递增子序列尾元素的长度
  • 转移方程:通过方程 res[i] = Math.max(res[i], nums[i] > nums[j] ? res[j] + 1 : 1),动态计算出各上升子序列的长度。
  • 倒序取值:res 数组进行倒序,第一个即为最大长度的值。
详解
  1. 1.
    如果给定数组长度小于等于 1,则最长上升子序列的长度等于数组长度。
  2. 2.
    初始化一个长度等于给定数组的长度,且元素都为 1 的数组 res。
  3. 3.
    当 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),通过转移方程收集
    各上升子序列的长度。
  4. 4.
    通过 sort 函数对 res 倒序排列,第一元素值 res[0] 就是最长的上升子序列长度。
1
/**
2
* @param {number[]} nums
3
* @return {number}
4
*/
5
const lengthOfLIS = function (nums) {
6
const len = nums.length;
7
if (len <= 1) {
8
return len;
9
}
10
// 初始化默认全为1
11
const res = new Array(len).fill(1);
12
for (let i = 1; i < len; i++) {
13
for (let j = 0; j < i; j++) {
14
// 转移方程
15
res[i] = Math.max(res[i], nums[i] > nums[j] ? res[j] + 1 : 1);
16
}
17
}
18
// 倒序
19
res.sort((a, b) => b - a);
20
return res[0];
21
};
Copied!
复杂度分析
  • 时间复杂度:
    O(n2)O(n^2)
  • 空间复杂度:
    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 即为最长的上升子序列长度。
1
/**
2
* @param {number[]} nums
3
* @return {number}
4
*/
5
const lengthOfLIS = function (nums) {
6
const len = nums.length;
7
if (len <= 1) {
8
return len;
9
}
10
const tail = new Array(len);
11
tail[0] = nums[0];
12
let end = 0;
13
for (let i = 1; i < len; i++) {
14
if (nums[i] > tail[end]) {
15
end += 1;
16
tail[end] = nums[i];
17
} else {
18
let left = 0;
19
let right = end;
20
// 二分查找
21
while (left < right) {
22
// 位运算,右移一位
23
const mid = left + ((right - left) >> 1);
24
if (tail[mid] < nums[i]) {
25
left = mid + 1;
26
} else {
27
right = mid;
28
}
29
}
30
tail[left] = nums[i];
31
}
32
}
33
return end + 1;
34
};
Copied!
复杂度分析
  • 时间复杂度:
    O(nlogN)O(nlogN)
    外层一个数组循环遍历,里面嵌套一个二分查找,所以是
    O(nlogN)O(nlogN)
  • 空间复杂度:
    O(n)O(n)
    创建的数组 tail 占用空间大小为 n,循环遍历中并没有分配新的空间

单词拆分

示例
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明
  • 拆分时可以重复使用字典中的单词。
  • 你可以假设字典中没有重复的单词。
  • 注意你可以重复使用字典中的单词。
示例 1:
1
输入: s = "leetcode", wordDict = ["leet", "code"]
2
输出: true
3
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
Copied!
示例 2:
1
输入: s = "applepenapple", wordDict = ["apple", "pen"]
2
输出: true
3
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
Copied!
示例 3:
1
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
2
输出: false
Copied!

方法一 暴力破解法

思路
把字符串 s 的前缀从短到长拆出来进行判断是否在单词字典中,若在字典中则把前缀截取掉继续递归,直到字符串的长度为 0。在递归中若遇到字符串任何长度的前缀都无法匹配到字典中的单词,则回溯到上层递归。
详解
1、检查字典中是否有字符串的前缀; 2、若有的话,将字符串去掉这个前缀后继续遍历,重复步骤 1、2; 3、若某次调用发现整个字符串都已拆分并且都在字典内则返回 true;
1
const wordBreak = function (s, wordDict) {
2
if (s.length === 0) {
3
return true;
4
}
5
for (let i = 0; i < wordDict.length; i += 1) {
6
const startIndex = s.indexOf(wordDict[i]);
7
if (startIndex === 0) {
8
// 将字符串去掉这个匹配到的前缀后继续遍历
9
const temp = s.slice(startIndex + wordDict[i].length);
10
if (wordBreak(temp, wordDict) === true) {
11
return true;
12
}
13
}
14
}
15
return false;
16
};
Copied!
  • 时间复杂度:最坏情况下是
    O(nn)O(n^n)
    ,因为考虑 s = 'aaaaaaaaaaaaaaaa', wordDict = ['a'],每一个字符都在字典中,此时递归的时间复杂度会达到
    O(nn) O(n^n)
    ,妥妥超时
  • 空间复杂度:
    O(1)O(1)
    ,循环中申请了 3 个临时变量,与输入的字符串的长度无关,空间占用属于常数阶,故空间复杂度为
    O(1)O(1)

方法二 动态规划

思路
dp[i] 表示字符串 s 从开始到 i 位置是否可以由 wordDict 组成。使用 j 从头开始遍历,若 dp[i] 可由 wordDict 组成,并且 ij 之间的单词可以在 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,则说明字符可由字段中的单词组合而成;
代码
1
const wordBreak = function (s, wordDict) {
2
const len = s.length;
3
const dp = new Array(len + 1).fill(false);
4
dp[0] = true;
5
for (let i = 1; i <= len; i++) {
6
for (let j = 0; j < i; j++) {
7
if (dp[j] && wordDict.includes(s.substring(j, i))) {
8
dp[i] = true;
9
break;
10
}
11
}
12
}
13
return dp[len];
14
};
Copied!
复杂度分析
  • 时间复杂度:
    O(n2)O(n^2)
    因为有两层循环,每层循环都从头遍历到尾。
  • 空间复杂度:
    O(n)O(n)
    因为只开辟了一个
    nn
    长度的数组。

方法三 动态规划(优化版)

思路
第二层遍历中不用每次遍历 i 的长度,只要遍历字典中最长单词的长度 maxStep 即可。
详解
1、第一层遍历:用 i 从头到尾遍历字符串; 2、第二层遍历:用 ji - maxStepi 遍历字符串; 3、若 dp[j] = true 而且字典中存在字符串 s[i~j],则说明 dp[i] = true; 4、继续步骤 1、2,直到整个字符串都遍历一遍; 5、若 dp[s.length()] = true,则说明字符可由字段中的单词组合而成;
1
const wordBreak = function (s, wordDict) {
2
const len = s.length;
3
const dp = new Array(len + 1).fill(false);
4
dp[0] = true;
5
// 计算单词的最长长度
6
let maxStep = 0;
7
for (let i = 0; i < wordDict.length; i++) {
8
if (wordDict[i].length > maxStep) {
9
maxStep = wordDict[i].length;
10
}
11
}
12
for (let i = 1; i <= len; i++) {
13
const startOfJ = i - maxStep > 0 ? i - maxStep : 0;
14
for (let j = startOfJ; j < i; j++) {
15
if (dp[j] && wordDict.includes(s.substring(j, i))) {
16
dp[i] = true;
17
break;
18
}
19
}
20
}
21
return dp[len];
22
};
Copied!
复杂度分析
  • 时间复杂度:
    O(n2)O(n^2)
    因为有两层循环,每层循环都从头遍历到尾。
  • 空间复杂度:
    O(n)O(n)
    因为最长只开辟了一个
    nn
    长度的数组。