力扣刷题-动态规划总结

106 阅读 0 评论 70 点赞

我是靠谱客的博主美好时光，这篇文章主要介绍力扣刷题-动态规划总结，现在分享给大家，希望可以做个参考。

力扣-动态规划

动态规划基础题目

按照如下顺序将力扣题目做完，相信会帮助你对动态规划基础问题有一个深刻的理解。
509.斐波那契数
70.爬楼梯
746.使用最小花费爬楼梯
62.不同路径
63.不同路径II
343.整数拆分
96.不同的二叉搜索树

动态规划的五个步骤：

确定 f 数组以及下标的含义
确定递推公式
f 的初始化
确定遍历顺序
举例推导dp数组

解法

509.斐波那契数
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

复制代码

1
2
3
4
5
6
7
8
9
10
var fib = function(n) {
    //动态规划
    let F=[0,1]
    //最低从2开始
    for(let i=2;i<=n;i++){
        F[i]=F[i-1]+F[i-2]
    }
    return F[n]
};

70.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

复制代码

1
2
3
4
5
6
7
8
9
10
11
var climbStairs = function(n) {
    //动态规划
    //f[i]第i阶楼梯又多少种方法爬到楼顶
    //f[i]=f[i-1]+f[i-2]
    let f=[1,2]
    for(let i=2;i<n;i++){
        f[i]=f[i-1]+f[i-2]
    }
    return f[n-1]
};

62.不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var uniquePaths = function(m, n) {
    //动态规划
    //从左上角到右下角的走法 = 从右边开始走的路径总数+从下边开始走的路径总数

    //先创建出数组对象
    let f=new Array(m).fill(0).map(()=>new Array(n).fill(0))
    //对边界值进行初始化，左下和右上只有一种走法
    for(let i=0;i<m;i++){
        f[i][0]=1
    }
    for(let j=0;j<n;j++){
        f[0][j]=1
    }
    for(let i=1;i<m;i++){
        for(let j=1;j<n;j++){
            f[i][j]=f[i-1][j]+f[i][j-1]
        }
    }
    return f[m-1][n-1]
};

63.不同路径II
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var uniquePathsWithObstacles = function(obstacleGrid) {
    let m=obstacleGrid.length,n=obstacleGrid[0].length
    let f=new Array(m).fill(0).map(()=>new Array(n).fill(0))
    //需要对临界进行判断，剔除掉有障碍物的路径
    for(let i=0;i<m && obstacleGrid[i][0]===0;i++){
            f[i][0]=1
    }
    for(let j=0;j<n &&obstacleGrid[0][j]===0;j++){
            f[0][j]=1
    }
    for(let i=1;i<m;++i){
        for(let j=1;j<n;++j){
            f[i][j]=obstacleGrid[i][j]===1?0:f[i-1][j]+f[i][j-1]
        }
    }
    return f[m-1][n-1]
};

343.整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var integerBreak = function(n) {
    //动态规划
    let f=new Array(n+1).fill(0)
    f[2]=1
    for(let i=3;i<=n;i++){
        for(let j=1;j<i;j++){
            //这里做一个判断，要么最大值是(i-j)*j;
            //要么在对i-j进行划分，也就是f[i-j]
            f[i]=Math.max(f[i],f[i-j]*j,(i-j)*j)
        }
    }
    return f[n]
};

96.不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var numTrees = function(n) {
    //动态规划
    //1.对于整数n，互不相同的二叉搜索数量 = 所有以1到n为根节点的组合数量之和。
    // 2.以i为根节点的组合数量 = 左子树节点组合数 * 右子树节点组合数。
    let f=new Array(n+1).fill(0)
    f[0]=1
    for(let i=1;i<=n;i++){
        for(let j=1;j<=i;j++){
        //对于第i个节点，需要考虑1作为根节点直到i作为根节点的情况，所以需要累加
        //一共i个节点，对于根节点j时,左子树的节点个数为j-1，右子树的节点个数为i-j
            f[i]+=f[j-1]*f[i-j]
        }
    }
    return f[n]
};