Jacky's blog
wangjiasheng
2021-01-03
目录

动态规划

核心：画出树形结构图，因为只有画出了树形结构图就知道动态规划到底如何去编写了！！

  • 递归 + 缓存：bottom 至 up

# 509.斐波那契数 (opens new window)

题解1：

  1. 画出树形结构图，根节点的值由下一层的子节点决定

    fib(5) <- fib(4) + fib(3)

    一般根据题意决定，return 的是连续值、离散值

  2. 需要准备一个缓存矩阵cache/memo/dp

  3. 构造递归函数：function recursion()

伪代码：

// 1. 构建缓存矩阵
const cache = [];
// 2. 构造递归函数
function recursion(n){
    // 2.1 写递归函数的截止条件
    if(return的值是否能通过缓存居中得到?){
       若能：直接return [连续值/离散值]
    }
    // 2.2 递归方程，斐波那契中当前值由下一层字节点决定
    cache[n] = recursion(n-1) + recursion(n-2)
    
    // 2.3 递归必须返回结果
    return [连续值/离散值]
}
// 3. 返回结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
点击查看

参考代码

var fib = function(n) {
    // 解法1 ： 递归 + 缓存

    //假装自己已经解决了该问题了： PrendFun(num)
    // 缓存区：
    const cache = [];
    cache[0] = 0;
    cache[1] = 1;

    function PrendFun(n){
        // 递归的截止条件：直接返回已知的值
        if(cache[n] !== undefined){
            console.log(cache[n]);
            return cache[n];
        }

        //  根据公式自己调用自己 
        cache[n] = PrendFun(n-1) + PrendFun(n-2);
        return cache[n];
    }

    const result = PrendFun(n);
    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

题解2

  • 根据递归逻辑，顺序return出各位置上的value【此种算法还存在空间优化写法】
  • 举例：已知fib(0),fib(1)，可以此得到fib(2),fib(3),...,f(n)

伪代码

// 1. 先写缓存矩阵
const cache = [];
cache[0] = 0;
cache[1] = 1;

// 2. 按照递归逻辑顺序得值
for(以此编列数组){
    以此得到对应的cache[i]
}
// 3. return 结果
1
2
3
4
5
6
7
8
9
10
点击查看

参考代码

var fib = function(n) {
    // 解法2： 自底向上，一个一个算
    const cache = [];
    cache[0] = 0 ;
    cache[1] = 1 ;
    for (let i=2;i<=n;i++){
        cache[i] = cache[i-1]+cache[i-2];
    }
    return cache[n];
};
1
2
3
4
5
6
7
8
9
10

# 55.跳跃游戏 (opens new window)

题解1：

  • 斐波那契的离散版本

    cache/memo直接三个值：0(未知)、-1(找不到)、1(找到)

  • 难点：画出树形结构图

    • 子节点全为-1,则根节点为-1
    • 只要有一路1，则根节点为1

伪代码：

// 1.构建缓存矩阵与设置初始条件
const memo = [];
memo[end结点] = -1;

// 2.递归函数：
function recursion(n){
    //2.1 截止条件
    if(return的值是否能通过缓存居中得到?){
       若能：直接return [离散值]
    }
    //2.2 递归方程
    //与斐波那契区别的是，根节点下有多少个子节点不清楚，需要自己去判断start index与end index
    for(let i=start index;i<end index;i++){
    	递归调用 recursion(i),只要根节点有1，则直接return 1
    }
    否则，memo[当前节点] = -1
    return false
}
// 返回结果
return jump(0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
点击查看

参考代码

var canJump = function(nums) {
    const totalLength = nums.length;//区别 Fib函数并没有预存空间
    const memo = Array(totalLength).fill(0);
    memo[totalLength - 1] = 1 ;// 这步类似fib函数

    // 递归函数：
    function jump(position){
        // 截止条件
        if(memo[position] === 1){
            return true;
        }else if(memo[position] === -1){
            return false;
        }

        // 递归方程，主要是解决0的情况
        const maxJump = Math.min(position + nums[position], totalLength-1);
        for(let i = position+1;i<=maxJump;i++){
            const jumpResult = jump(i);
            if(jumpResult === true){
                memo[position] = 1;
                return true;
            }
        }
        memo[position] = -1;
        return false;
    }
    let result = jump(0);
    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
28
29

题解2：

  • 同斐波那契序列，根据递归逻辑，顺序return出各位置上的value，只不过跳跃游戏中该value比较隐式
    • 首先，定义return的value有两类：0 和 1
    • 起始点：memo[end] = 1，依次迭代可得memo[end-1]，memo[end-2]，......，memo[0]
    • 直接return memo[0]

伪代码：

//1. 缓存矩阵及初始值
const memo = [];
memo[end] = 1  ;

//2. 从后往前顺序计算memo
for(从后往前计算,end-1,end-2,...,0){
    // 计算根节点，因为不同于斐波那契函数，此根节点的数目不确定
    for(根节点循环){
        if(一旦memo中存在1){
            //1.设置当前位置的memo[i]为1
            //2.找到以后就无序再找了，所以直接break就可以了。
        }
    }
}
//3. return memo[0] 从缓存矩阵中读取
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
点击查看

参考代码：

var canJump = function(nums) {
    const memo = Array(nums.length).fill(0);
    memo[nums.length - 1] = 1;
    for(let i = nums.length-2;i>=0;i--){
        const maxJump = Math.min(nums.length-1, nums[i]+i);
        for(let j=i+1;j<=maxJump;j++){
            if(memo[j] === 1){
                memo[i] = 1;
                break;
            }
        }
    }
    // 这里memo状态只需要1和0,无序要设置-1，所以memo返回的矩阵[0 0 0 1]等
    if(memo[0]==1){
        return true
    }else{
        return false
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 70.爬楼梯 (opens new window)

题解：

  • 基本理解了斐波那契数列那道题，此题就可以轻松解决。
  • 区别是：cache缓存矩阵的大小
    • 可以是空矩阵，截止条件判断cache矩阵中是否已有缓存值【!== undefined】
    • 也可以提前设置一个大小已知的矩阵Array(n).fill(0 or null)，截止条件判断cache矩阵中是否已有缓存值【!== null】
点击查看

参考代码：

  • 递归 + 缓存
var climbStairs = function(n) {
    // 递归 + 缓存版本
    const cache = [];
    cache[1] = 1;
    cache[2] = 2;

    function f(n){
        if( cache[n] != undefined ){
            return cache[n]
        }
        // 未定义就要计算
        cache[n] = f(n-1) + f(n-2);
        return cache[n];
        }
    return f(n);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  • 按照缓存方向顺序迭代
var climbStairs = function(n) {
    // 按照缓存方向顺序迭代，设置初始迭代值
    const cache = [];
    cache[1] = 1;
    cache[2] = 2;

    for(let i=3;i<=n;i++){
        cache[i] = cache[i-1] + cache[i-2];
    }
    return cache[n];
};
1
2
3
4
5
6
7
8
9
10
11
  • 继续优化空间，已知下一个位置只需要两个变量可得，那就只开两个变量缓存中间值。
var climbStairs = function(n) {
    // 按照缓存方向顺序迭代[双变量缓存版]
    pre = 1;
    cur = 2;
    for(let i=3;i<=n;i++){
        cur2 = pre + cur;
        pre = cur;
        cur = cur2;
    }
    if(n==1 || n==2){
        return n
    }else{
        return cur
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 198.打家劫舍 (opens new window)

题解：

  • 非常简单的一道题

  • cache保存各位置能偷到的最大利润，更新原则：当前的最大利润 = 当前值 + Math.max(前隔一个位置以前利润的最大值)

    MaxProfit 存放前隔一个位置以前利润的最大值。

点击查看

参考代码：

var rob = function(nums) {
    if(nums.length<1){
        return nums.length
    }else if(nums.length==1 ){
        return nums[0]
    }else if(nums.length==2){
        return Math.max(...nums)
    }
    
    const cache = Array(nums.length);
    cache[0] = nums[0];
    cache[1] = nums[1];
    maxProfit = nums[0];
    for(let i =2;i<nums.length;i++){
        cache[i] = maxProfit + nums[i];
        maxProfit = Math.max(cache[i-1], maxProfit);
    };
    // console.log(cache)
    return Math.max(...cache);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 238.除自身以外数组的乘积 (opens new window)

题解：

  • 知识点：两遍动态规划
  • 第1遍：cache存放的是从左至[当前位置-1]的乘积
  • 第2遍：cache存放的是从右至[当前位置+1]的乘积

伪代码：

// 定义缓存矩阵 result
// 原矩阵：product=1 -> [1,2,3,4]
// 第一遍动态规划：[1,1,2,6] <- product=1
// 第二遍动态规划：[24,12,8,6] -> return
1
2
3
4
点击查看

参考代码：

var productExceptSelf = function(nums) {
    const result = Array(nums.length).fill(1);
    let product = 1;
    for(let i=0;i<nums.length;i++){
        // 1 [1,1,1,1]; 
        // product 记录的是前一个值的乘积
        result[i] = product * result[i];
        product = product * nums[i]; // product 更新
    }

    product = 1;
    for(let i=nums.length-1;i>=0;i--){
        // 1 [1,1,1,1]; 
        // product 记录的是前一个值的乘积
        result[i] = product * result[i];
        product = product * nums[i]; // product 更新
    }
    return result ;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 53.最大子序列和 (opens new window)

题解：

  • 循环遍历一次数组，记录每个索引值上的最大的数组和。

  • 最大值求解规则：

    如：[-2,1,-3,4,-1,2,1,-5,4]
缓存中间的最大值：
   [-2,1,-2,4,3,5,6,1,5]
动态规划问题：
	状态转移方程：当前最大值 =  max(前值最大值 + 当前值,当前值)
    1
    2
    3
    4
    5
点击查看

参考答案：

var maxSubArray = function(nums) {
    // 上一个值的最大值
    let memo = 0;
    // 缓存中间结果
    let max = nums[0];

    for(let i=0 ;i<nums.length;i++){
        memo = Math.max(memo + nums[i] , nums[i]);
        max = Math.max(max,memo);
    }
    return max
};
1
2
3
4
5
6
7
8
9
10
11
12

# 152.乘积最大子数组 (opens new window)

题解：

  • 思路同同53题最大子序列和，唯一不同的时候，需要负数存在的情况
  • 缓存矩阵的思考
    • cache1存当前位置以前的最大值
    • cache2存当前位置以前的最小值【负数情况】
    • 两个缓存矩阵交替决定：nums[i]、cache1[i] * nums[i]、cache2[i] * nums[i]

伪代码：

// 先决定cache1[0],cache2[0]
for(从i=1开始遍历数组){
    更新cache1
    更新cache2
}
return cache1中的最大值
1
2
3
4
5
6
点击查看

参考代码：

  • 自底向上，顺序决定递归值
var maxProduct = function(nums) {
    let cache1 = [];// cache1 保存当前位置的最大乘积
    cache1[0] = nums[0];
    let cache2 = [];// cache1 保存当前位置的最小乘积
    cache2[0] = nums[0];
    for(let i=1;i<nums.length;i++){
        cache1[i] = Math.max(cache1[i-1] * nums[i], cache2[i-1] * nums[i], nums[i]);
        cache2[i] = Math.min(cache1[i-1] * nums[i], cache2[i-1] * nums[i], nums[i]);
    }
    return Math.max(...cache1);
};
1
2
3
4
5
6
7
8
9
10
11

  • 同样该动规问题可以由递归+缓存决定

    recursionMax(n) 返回的是当前乘积的最大值【根】<-- recursionMax(n-1)、recursionMin(n-1)、nums[n]【叶】

var maxProduct = function(nums) {
if(nums.length == 1){
    return nums
}

// 缓存矩阵
const memoMax = Array(nums.length).fill(null);
const memoMin = Array(nums.length).fill(null);
memoMax[0] = nums[0];
memoMin[0] = nums[0];
var result = nums[0];

// 最大递归函数
function recursionMax(n){
    if(memoMax[n] != null){
        return memoMax[n]
    };
    // 转移方程
    memoMax[n] = Math.max(recursionMax(n-1)*nums[n],nums[n],recursionMin(n-1)*nums[n]);
    result = Math.max(result, memoMax[n]);
    return memoMax[n];
}
function  recursionMin(n){
    if(memoMin[n] != null){
        return memoMin[n]
    };
    memoMin[n] = Math.min(recursionMax(n-1)*nums[n],nums[n],recursionMin(n-1)*nums[n]);
    return memoMin[n];
}
recursionMax(nums.length-1);
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
28
29
30
31
32

# 62. 不同路径

题解：

  • 知识点：二维动态规划
点击查看

参考代码：

  • 递归 + 缓存
var uniquePaths = function(m, n) {
    // js中二维空矩阵的创建：
    memo = [];
    // 矩阵的创建：通过数组实现，索引[行][列]
    for(let i=0;i<m;i++){
        memo.push(Array(n).fill(0));
    };

    for(let i = 0; i<m ;i++){
        memo[i][0] = 1;
    };
    for(let j = 0; j<n ;j++){
        memo[0][j] = 1;
    };

    // 编写递归函数
    function recurision(m,n){
        // 截止条件
        if( memo[m-1][n-1] !== 0 ){
            return memo[m-1][n-1]
        }
        
        memo[m-1][n-1] = recurision(m-1,n) + recurision(m,n-1);
        return memo[m-1][n-1];
    }
    return recurision(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
  • 顺序迭代
var uniquePaths = function(m, n) {
    // js中二维空矩阵的创建：
    memo = [];
    // 矩阵的创建：通过数组实现，索引[行][列]
    for(let i=0;i<m;i++){
        memo.push(Array(n).fill(0));
    };

    for(let i = 0; i<m ;i++){
        memo[i][0] = 1;
    };
    for(let j = 0; j<n ;j++){
        memo[0][j] = 1;
    };

    // 自底向上递归
    for(let i=1;i<m;i++){
        for(let j=1;j<n;j++){
            memo[i][j] = memo[i-1][j] + memo[i][j-1];
        }
    }
    return memo[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

# 121.买卖股票的最佳时机 (opens new window)

题解：

  • 此题：看似非动态规划，实为动规。

    此题为简单题，若一开始没有想通，其实也很好编写出来，但是一旦相同了是动规问题，则可直接套用动规的模板写法，思路清晰简介。

点击查看

参考代码:

  • 模板写法，只要掌握了标准写法，可随时修改为递归 + 缓存版本
var maxProfit = function(prices) {
// 此题：看似非动态规划，实则每一个位置的值仍需要迭代才能确定
// 思考：什么值需要迭代才能知道？minVal[i] <- minVal[i-1], prices[i]
// maxProfit <-- prices[i] - minVal

let maxProfit = 0;
const minVal = [];
minVal[0] = prices[0];
for(let i=1;i<prices.length;i++){
    minVal[i] = Math.min(minVal[i-1],prices[i]);
    maxProfit = Math.max(maxProfit,prices[i]-minVal[i]);
}
return maxProfit;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  • 思路不清晰版本，浮动minPrice
var maxProfit = function(prices) {
if(prices.length === 0 ){
        return 0;
}
let minPrice = prices[0];
let maxProfit = Array(prices.length).fill(0);
for(let i=1;i<prices.length;i++){
    maxProfit[i] = prices[i] - minPrice;
    minPrice = Math.min(minPrice, prices[i]);
};
return Math.max(...maxProfit);
}
1
2
3
4
5
6
7
8
9
10
11
12

# 122.买卖股票的最佳时机 II (opens new window)

题解：

  • 此题虽然是上一题的继承，但是各位置的不存在迭代关系，即i-1与i位置上的数据没有关系

    故，此题为非动态规划问题

  • 不停地找peak和valley，并将值累加起来

点击查看

参考代码：

var maxProfit = function(prices) {
    if (prices.length  ===0 ){
        return 0;
    }
    var peak = prices[0];
    var valley = prices[0];
    var profit = 0;
    let i = 0 ;
    while( i< prices.length-1){
        while(i< prices.length-1 && prices[i]>=prices[i+1]){
            i++;
        }
        valley = prices[i];
        while(i< prices.length-1 && prices[i]<=prices[i+1]){
            i++;
        }
        peak = prices[i];
        profit += peak - valley;
    }
    return profit
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 贪心算法

# 134.加油站 (opens new window)

题解：

  • 知识点：贪心算法

    注意点

    • 贪心算法大多题目靠背答案，所以如果能用动态规划就尽量用动规，不用贪心算法

  • 核心：变量currentGas记录当前节点i的剩余油量

    该值 = i-1加油站的剩余油量 + i加油站的添加油量 - 到i站点花费的油量。

    这里贪心做的一个操作：对currentGas做了一个Relu激活函数

点击查看

参考代码：

var canCompleteCircuit = function(gas, cost) {
let totalGas = 0;
for(let i=0;i<gas.length;i++){
    totalGas += gas[i];
}
let totalCost = 0;
for(let i=0;i<cost.length;i++){
    totalCost += cost[i];
}

if(totalGas < totalCost){
	return -1;
}

let currentGas = 0;
let start = 0;
for(let i=0;i<gas.length;i++){
	currentGas = currentGas - cost[i] + gas[i];
	if (currentGas < 0) {
		currentGas = 0;
		start = i + 1;
	}
}
return start;
};
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
编辑 (opens new window)
#刷题
上次更新: 2022/04/06, 15:04:00
链表题
双指针

← 双指针→

最近更新
01
如何理解浏览器的 user agent 用户代理的含义?
11-05
02
浏览器事件循环机制
10-31
03
浏览器页面渲染机制【2023】
10-15
更多文章>
Theme by Vdoing | Copyright © 2020-2023