跟着代码随想录练算法 —— 动态规划（JS）

62. 不同路径

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    let dp = new Array(m)
    dp[0] = new Array(n)
    dp[0].fill(1)
    for(let i = 1; i < m; i++){
        dp[i] = new Array(n)
        for(let j = 0; j < n; j++){
            if(j === 0) dp[i][0] = 1
            else dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    return dp[m-1][n-1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

63. 不同路径 II

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    let m = obstacleGrid.length
    let n = obstacleGrid[0].length
    let dp = new Array(m)
    // 初始化数组
    for(let i = 0; i < m; i++){
        dp[i] = new Array(n)
        if(i === 0) dp[0][0] = !obstacleGrid[0][0]
        else{
            if(obstacleGrid[i][0] === 1) dp[i][0] = 0
            else dp[i][0] = dp[i-1][0]
        }
    }
    for(let i = 1; i < n; i++){
        if(obstacleGrid[0][i] === 1){
            dp[0][i] = 0
        }else{
            dp[0][i] = dp[0][i-1]
        }
    }
    console.log(dp)
    for(let i = 1; i < m; i++){
        for(let j = 1; j < n; j++){
            if(obstacleGrid[i][j] === 1){
                dp[i][j] = 0
            }else{
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            }
        }
    }
    return dp[m-1][n-1]
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

96. 不同的二叉搜索树

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    let dp = new Array(n+1)
    dp[0] = 1
    dp[1] = 1
    for(let i = 2; i <= n; i++){
        dp[i] = 0
        for(let j = 0; j <= i - 1; j++){
            dp[i] += dp[j]*dp[i-j-1]
        }
    }
    return dp[n]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

343. 整数拆分

/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function(n) {
    let  dp = new Array(n)
    dp[2] = 1
    for(let i = 3 ; i <= n; i++){
        dp[i] = Math.max(1*(i-1), 1*dp[i-1])
        for(let j = 2; j <= i -2; j++){
            dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]))
        }
        // console.log(`dp[${i}]=${dp[i]}`)
    }
    return dp[n]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

416. 分割等和子集

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function(nums) {
    let sum = 0
    for(let i = 0; i < nums.length; i++){
        sum += nums[i]
    }
    if(sum%2 !== 0) return false
    let n = sum/2
    let dp = new Array(n+1).fill(0)
    dp[0] = 0
    for(let i = 0; i < nums.length; i++){
        for(let j = n; j >= nums[i]; j--){
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i])
        }
        // console.log(dp)
    }
    if(dp[n] === n) return true
    return false
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1049. 最后一块石头的重量 II

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeightII = function(stones) {
    let sum = 0
    for(let i = 0; i < stones.length; i++){
        sum += stones[i]
    }
    let a = Math.floor(sum/2)
    let dp = new Array(a+1).fill(0)
    for(let i = 0; i < stones.length; i++){
        for(let j = a; j >= stones[i]; j--){
            dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i])
        }
    }
    return (sum - dp[a]) - dp[a]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

494. 目标和

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function(nums, target) {
    let sum = 0
    for(let i = 0; i < nums.length; i++){
        sum += nums[i]
    }
    if((sum + target) % 2 !== 0 ) return false
    if( sum < target) return false
    let left = (sum + target) / 2
    if(left < 0) return false
    let dp = new Array(left + 1).fill(0)
    dp[0] = 1
    for(let i = 0; i < nums.length; i++){
        for(let j = left; j >= nums[i]; j--){
            dp[j] += dp[j - nums[i]]
        }
    }
    return dp[left]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

474. 一和零

/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var findMaxForm = function(strs, m, n) {
    // 统计每个str的0,1个数
    let zeroArr = new Array(strs.length).fill(0)
    let oneArr = new Array(strs.length).fill(0)
    for(let i = 0; i < strs.length; i++){
        let str = strs[i].split('')
        str.forEach((char) => {
            if(char == 0) zeroArr[i] ++
            else if(char == 1) oneArr[i] ++
        })
    }
    // console.log(zeroArr,oneArr)
    // 初始化dp数组
    let dp = new Array()
    for(let i = 0; i <= m; i++){
        dp.push(new Array(n+1).fill(0))
    }
    for(let k = 0; k < strs.length; k++){
        for(let i = m; i >= zeroArr[k]; i--){
            for(let j = n; j >= oneArr[k]; j--){
                // 更新dp
                dp[i][j] = Math.max(dp[i][j], dp[i-zeroArr[k]][j-oneArr[k]]+1)
                // console.log(i,j,dp)
            }
        }
    }
    
    return dp[m][n]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

518. 零钱兑换 II

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function(amount, coins) {
    let dp = new Array(amount + 1).fill(0)
    dp[0] = 1
    for(let i  = 0; i < coins.length; i++){
        for(let j = coins[i]; j <= amount; j++){
            dp[j] += dp[j - coins[i]]
        }
        // console.log(dp)
    }
    return dp[amount]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

377. 组合总和 Ⅳ

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var combinationSum4 = function(nums, target) {
    let dp = new Array(target + 1).fill(0)
    dp[0] = 1
    for(let i = 1; i <= target; i++){
        for(let j = 0; j < nums.length; j++){
            if(i >= nums[j]){
                dp[i] += dp[i - nums[j]]
            }
        }
    }
    return dp[target]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

70. 爬楼梯(完全背包做法)

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let dp = new Array(n+1).fill(0)
    dp[0] = 1
    for(let j = 1; j <= n ;j++){
        for(let i = 1; i <= 2; i++){
            if(j >= i){
                dp[j] += dp[j - i]
            }
        }
    }
    return dp[n]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

322. 零钱兑换

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    let dp = new Array(amount + 1).fill(Infinity)
    dp[0] = 0
    for(let i = 0; i < coins.length; i++){
        for(let j = coins[i]; j <= amount; j++){
            dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1)
        }
    }
    // console.log(dp)
    return dp[amount] === Infinity ? -1 : dp[amount]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

279. 完全平方数

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    let dp = new Array(n + 1).fill(Infinity)
    dp[0] = 0
    let num = Math.sqrt(n)
    if(num % 1 === 0) return 1
    num = Math.floor(num)
    for(let i = 1; i <= num; i++){
        for(let j = i*i; j <= n; j++){
            dp[j] = Math.min(dp[j], dp[j - i*i] + 1)
        }
    }
    return dp[n]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

139. 单词拆分

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    let n = s.length
    let dp = new Array( n + 1).fill(false)
    dp[0] = true
    let set = new Set(wordDict)
    for(let i = 0; i <= n; i++){
        for(let j = 0; j < i; j++){
            let str = s.substr(j, i - j)
            if(set.has(str) && dp[j]){
                dp[i] = true
            }
        }
    }
    console.log(dp)
    return dp[n]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

198. 打家劫舍

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if(nums.length === 1) return nums[0]
    let dp = new Array(nums.length)
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1])
    for(let i = 2; i < nums.length; i++){
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])
    }
    return dp[nums.length - 1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

213. 打家劫舍 II

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if(nums.length === 1) return nums[0]
    function fn(start, end){
        // 如果考虑的情况只有一个 直接返回这个金额
        if(start === end) return nums[end]
        let dp = new Array(nums.length - 1)
        dp[0] = nums[start]
        dp[1] = Math.max(nums[start], nums[start+1])
        for(let i = 2; i <= dp.length - 1; i++){
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i + start])
        }
        console.log('dp:',dp)
        return dp[dp.length - 1]
    }
    return Math.max(fn(0, nums.length - 2), fn(1, nums.length - 1))
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

337. 打家劫舍 III

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function(root) {
    function backtracking(node){
        if(node === null) return [0, 0]
        // 拿到左右子树的返回结果
        let left = backtracking(node.left)
        let right = backtracking(node.right)
        // 不拿当前节点 左右节点都可以考虑（选择拿或者不拿其中较大者）
        let val1 =  Math.max(left[0], left[1]) + Math.max(right[0], right[1])
        // 拿当前节点 左右节点则不能考虑
        let val2 = node.val + left[0] + right[0]
        return [val1,val2]
    }
    let dp = backtracking(root)
    return Math.max(dp[0], dp[1])
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

121. 买卖股票的最佳时机

贪心

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let min = prices[0]
    let max = 0
    for(let i = 1; i < prices.length; i++){
        max = Math.max(max, prices[i] - min)
        min = Math.min(min, prices[i])
    }
    return max
};
1
2
3
4
5
6
7
8
9
10
11
12
13

动态规划

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let dp = new Array(prices.length)
    for(let i = 0; i < prices.length; i++){
        dp[i] = [0,0]
    }
    dp[0][0] = -prices[0]
    dp[0][1] = 0
    for(let i = 1; i < prices.length; i++){
        dp[i][0] = Math.max(dp[i-1][0], -prices[i])
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i])
    }
    return dp[dp.length - 1][1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

贪心

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if(prices.length <= 1) return 0
    let count = 0
    for(let i = 1; i < prices.length; i++){
        if(prices[i] - prices[i-1] > 0)
            count += prices[i] - prices[i-1]
    }
    return count
};
1
2
3
4
5
6
7
8
9
10
11
12
13

动态规划

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let dp = new Array(prices.length)
    for(let i = 0; i < prices.length; i++){
        dp[i] = [0,0]
    }
    dp[0][0] = -prices[0] // 持有股票所得金额
    dp[0][1] = 0            // 不持有股票所得金额
    for(let i = 1; i < prices.length; 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[dp.length - 1][1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let dp = new Array(prices.length)
    for(let i = 0; i < prices.length; i++){
        dp[i] = [0,0,0,0,0]
    }
    dp[0][1]  = dp[0][3] = -prices[0]
    for(let i = 1; i < prices.length; i++){
        dp[i][0] = dp[i-1][0]
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i])
        dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] + prices[i])
        dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] - prices[i])
        dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3] + prices[i])
    }
    return dp[dp.length - 1][4]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

188. 买卖股票的最佳时机 IV

/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(k, prices) {
    if(k === 0) return 0
    if(prices.length === 0) return 0 
    let dp = new Array(prices.length)
    for(let i = 0; i < prices.length; i++){
        dp[i] = new Array(2*k+1)
    }
    dp[0][0] = 0
    for(let j = 1; j < 2*k + 1; j++){
        if(j % 2 === 0){
            dp[0][j] = 0
        }else dp[0][j] = -prices[0]
    }
    
    for(let i = 1; i < prices.length; i++){
        for(let j = 0; j < 2*k - 1; j += 2){
            if(j === 0) dp[i][0] = dp[i-1][0]
            // 买入
            dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] - prices[i])
            // 卖出
            dp[i][j+2] = Math.max(dp[i-1][j+2], dp[i-1][j+1] + prices[i])
        }
    }
    return dp[prices.length-1][2*k]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

309. 最佳买卖股票时机含冷冻期

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if(prices.length === 1) return 0
    let dp = new Array(prices.length)
    for(let i = 0; i < prices.length; i++){
        dp[i] = [0,0,0,0]
    }
    dp[0][0] = -prices[0]
    for(let i = 1; i < prices.length; i++){
        // 买入股票状态 1.保持之前的买入状态 2.前一天冷冻/前一天过了冷冻 今天买入
        dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i],dp[i-1][3]-prices[i])
        // 卖出股票并且过了冷冻期状态 前一天是冷冻期/保持前一天的卖出状态
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][3])
        // 今天卖出股票 前一天是买入状态
        dp[i][2] = dp[i-1][0] + prices[i]
        // 今天是冷冻期 前一天卖出股票
        dp[i][3] = dp[i-1][2]
    }
    // 返回卖出状态 今日卖出 今日冷冻期 三者的最大金额
    return Math.max(dp[dp.length-1][1],dp[dp.length-1][2],dp[dp.length-1][3]) 
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

714. 买卖股票的最佳时机含手续费

贪心

/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {
    let result = 0
    let min = prices[0]
    for(let i = 1; i < prices.length; i++){
        // 1. 更新最低价格 相当于前一次已经将股票卖出 现在确定最低的买入价格
        if(prices[i] < min){
            min = prices[i]
        }
        
        // 2. 此时如果未拥有股票买入不划算 如果拥有股票卖出会亏本 保持现状
        if(prices[i] >= min && prices[i] <= min + fee){
            continue
        }
        
        // 3. 计算利润
        if(prices[i] > min + fee){
            result += prices[i] - min - fee
            min = prices[i] - fee
        }
    }
    return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

动态规划

/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {
    if(prices.length === 1) return 0
    let dp = new Array(prices.length)
    for(let i = 0; i < prices.length; i++){
        dp[i] = [0, 0]
    }
    dp[0][0] = -prices[0]
    for(let i = 1; i < prices.length; 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] - fee)
    }
    return dp[dp.length-1][1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

300. 最长递增子序列

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    let dp = new Array(nums.length).fill(1)
    let result = 1
    for(let i = 1; i < nums.length; i++){
        for(let j = 0; j < i; j++){
            if(nums[i] > nums[j])
            dp[i] = Math.max(dp[i],dp[j] + 1)
        }
        result = Math.max(result,dp[i])
    }
    // console.log(dp)
    return result
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

674. 最长连续递增序列

/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfLCIS = function(nums) {
    let dp = new Array(nums.length).fill(1)
    let result = 1
    for(let i = 1; i < nums.length; i++){
        if(nums[i] > nums[i-1]){
            dp[i] = dp[i-1] + 1
        }
        result = Math.max(result, dp[i])
    }
    return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

718. 最长重复子数组

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findLength = function(nums1, nums2) {
    let dp = new Array(nums1.length+1)
    for(let i = 0; i <= nums1.length; i++){
        dp[i] = new Array(nums2.length + 1).fill(0)
    }
    let ans = 0
    for(let i = 1; i <= nums1.length; i++){
        for(let j = 1; j <= nums2.length; j++){
            if(nums1[i-1] == nums2[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1
            }
            ans = Math.max(ans, dp[i][j])
        }
    }
    return ans
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1143. 最长公共子序列

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
    let dp = new Array(text1.length + 1)
    for(let i = 0; i <= text1.length; i++){
        dp[i] = new Array(text2.length + 1).fill(0)
    }
    let ans = 0
    for(let i = 1; i <= text1.length; i++){
        for(let j = 1; j <= text2.length; 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])
            }
            ans = Math.max(ans, dp[i][j])
        }
    }
    return ans
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1035. 不相交的线

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var maxUncrossedLines = function(nums1, nums2) {
    let dp = new Array(nums1.length + 1)
    for(let i = 0; i <= nums1.length; i++){
        dp[i] = new Array(nums2.length+1).fill(0)
    }
    let ans = 0
    for(let i = 1; i <= nums1.length; i++){
        for(let j = 1; j <= nums2.length; j++){
            if(nums1[i-1] == nums2[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])
            }
            ans = Math.max(ans, dp[i][j])
        }
    }
    return ans
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

53. 最大子数组和

贪心

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    if(nums.length === 1) return nums[0]
    let count = 0
    let max = -10000
    for(let i = 0; i < nums.length; i++){
        count += nums[i]
        max = Math.max(count, max)
        // console.log('max, count',max, count)
        if(count < 0){
            count = 0
        }
    }
    return max
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

动态规划

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let dp = new Array(nums.length)
    dp[0] = nums[0]
    let ans = nums[0]
    for(let i = 1; i < nums.length; i++){
        dp[i] = Math.max(dp[i-1] + nums[i], nums[i])
        ans = Math.max(ans, dp[i])
    }
    return ans
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

392. 判断子序列

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
    let dp = new Array(s.length+1)
    for(let i = 0; i <= s.length; i++){
        dp[i] = new Array(t.length+1).fill(0)
    }
    for(let i = 1; i <= s.length; i++){
        for(let j = 1; j <= t.length; j++){
            if(s[i-1] == t[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1
            }else{
                dp[i][j] = dp[i][j-1]
            }
        }
    }
    return dp[s.length][t.length] == s.length
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

115. 不同的子序列

/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var numDistinct = function(s, t) {
    let dp = new Array(s.length+1)
    for(let i = 0; i <= s.length; i++){
        dp[i] = new Array(t.length + 1).fill(0)
        dp[i][0] = 1
    }
    for(let i = 1; i <= s.length; i++){
        for(let j = 1; j <= t.length; j++){
            if(s[i-1] == t[j-1]){
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
            }else{
                dp[i][j] = dp[i-1][j]
            }
        }
    }
    return dp[s.length][t.length]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

583. 两个字符串的删除操作

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    let dp = new Array(word1.length + 1)
    for(let i = 0; i <= word1.length; i++){
        dp[i] = new Array(word2.length+1)
        dp[i][0] = i
    }
    for(let j = 0; j <= word2.length; j++){
        dp[0][j] = j
    }
    for(let i = 1; i <= word1.length; i++){
        for(let j = 1; j <= word2.length; 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][j-1] + 1, dp[i-1][j-1] + 2)
            }
        }
    }
    return dp[word1.length][word2.length]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

72. 编辑距离

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    let dp = new Array(word1.length+1)
    for(let i = 0; i <= word1.length; i++){
        dp[i] = new Array(word2.length+1)
        dp[i][0] = i
    }
    for(let j = 0; j <= word2.length; j++){
        dp[0][j] = j
    }
    for(let i = 1; i <= word1.length; i++){
        for(let j = 1; j <= word2.length; 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][j-1] + 1, dp[i-1][j-1] + 1)
            }
        }
    }
    return dp[word1.length][word2.length]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

647. 回文子串

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    let dp = new Array(s.length)
    for(let i = 0; i < s.length; i++){
        dp[i] = new Array(s.length).fill(false)
    }
    let ans = 0
    for(let i = s.length - 1 ; i >= 0; i --){
        for( let j = i; j < s.length; j ++){
            if(s[i] == s[j]){
                if( (j - i) <= 1){
                    dp[i][j] = true
                    
                }else{
                    dp[i][j] = dp[i+1][j-1]
                }
            }
            if(dp[i][j]) ans ++
        }
    }
    return ans
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

516. 最长回文子序列

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function(s) {
    let dp = new Array(s.length)
    for(let i = 0; i < s.length; i++){
        dp[i] = new Array(s.length).fill(0)
        dp[i][i] = 1
    }
    for(let i = s.length - 1; i >=0 ; i--){
        for(let j = i+1; j < s.length; j++){
            if(s[i] == s[j]){
                dp[i][j] = dp[i+1][j-1] + 2
            }else{
                dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j])
            }
        }
    }
    return dp[0][s.length-1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21