🌙 动态规划 (opens new window)
🌙 1.编辑距离 (opens new window)
🌙 2.滑动窗口最大值 (opens new window)
🌙 3.滑动窗口中位数 (opens new window)
🌙 4.最长上升子序列 (opens new window)
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function(nums) {
if(!nums || !nums.length) return 0;
let dp = new Array(nums.length).fill(1);
for(let i=0; i<nums.length; i++) {
for(let j=i; j>=0; j--) {
if(nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
🌙 5.剪绳子 (opens new window)
🌙 6.剪绳子 II (opens new window)
🌙 7.有效的字母异位词 (opens new window)
🌙 8.N 皇后 (opens new window)
🌙 9.N皇后 II (opens new window)
🌙 10.买卖股票的最佳时机 (opens new window)
🌙 11.买卖股票的最佳时机 II (opens new window)
🌙 12.买卖股票的最佳时机 III (opens new window)
🌙 13.买卖股票的最佳时机 IV (opens new window)
🌙 14.买卖股票的最佳时机含手续费 (opens new window)
🌙 15.最佳买卖股票时机含冷冻期 (opens new window)
🌙 16.打家劫舍 (opens new window)
🌙 17.打家劫舍 II (opens new window)
🌙 18.打家劫舍 III (opens new window)
🌙 19.岛屿数量 (opens new window)
🌙 20.零钱兑换 (opens new window)
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function(coins, amount) {
if (amount === 0) return 0;
let dp = [];
for (let i = 0; i <= amount; i++) {
dp[i] = amount + 1;
}
dp[0] = 0;
for (let i = 0; i <= amount; i++) {
for (let j = 0; j < coins.length; j++) {
if (i >= coins[j]) {
dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i])
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22