leetcode-notes-20230915

Last updated on 2023年9月16日 早上

509. 斐波那契数（C++动态规划实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int fib(int n) {
        if(n <= 1){
            return n;
        }
        //使用动态规划实现
        //定义状态数组，长度为n+1
        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2;i <= n;i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

70. 爬楼梯（C++动态规划实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int climbStairs(int n) {
        if(n <= 1){
            return n;
        }
        
        //思路：假设dp[i]表示达到第i阶楼梯所有可能的方法种类数量
        vector<int> dp(n + 1);
        //dp[0] = 0;//不需要考虑n=0的情况，因为n>=1
        dp[1] = 1;
        dp[2] = 2;//可以走两步，也可以连续走一步
        //由于dp[i]可以由dp[i - 1]增加一阶得到也可以由dp[i - 2]增加两阶得到
        //因此dp[i] = dp[i - 1] + dp[i - 2]
        //从前向后遍历
        for(int i = 3; i <= n;i ++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};


70. 爬楼梯（C++动态规划实现，优化空间的写法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int climbStairs(int n) {
        if(n <= 1){
            return n;
        }
        //优化空间的写法
        int dp[3];
        dp[1] = 1;
        dp[2] = 2;

        for(int i = 3;i <= n;i++){
            int sum = dp[1] + dp[2];
            dp[1] = dp[2];
            dp[2] = sum;
        }

        return dp[2];
    }
};

746. 使用最小花费爬楼梯（C++动态规划实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        //思路：使用一维dp数组，dp[i]表示跳到i层需要的最少花费
        //dp[i]可以由dp[i - 1]得到，此时的dp[i] = dp[i - 1] + cost[i - 1];
        //dp[i]也可以由dp[i - 2]得到，此时的dp[i] = dp[i - 2] + cost[i - 2];
        //那么dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        //初始化dp数组：dp[0] = 0; dp[1] = 0;
        
        // 定义dp数组
        vector<int> dp(cost.size() + 1);
        dp[0] = 0;
        dp[1] = 0;

        for(int i = 2;i <= cost.size();i++){
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[cost.size()];
    }
};

746. 使用最小花费爬楼梯（C++动态规划实现，优化内存空间）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        //优化空间复杂度
        int dp[3];
        dp[0] = 0;
        dp[1] = 0;

        for(int i = 2;i <= cost.size();i++){
            dp[2] = min(dp[1] + cost[i - 1], dp[0] + cost[i - 2]);
            dp[0] = dp[1];
            dp[1] = dp[2];
        }

        return dp[1];
    }
};

62. 不同路径（C++动态规划实现）

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
class Solution {
public:
    int uniquePaths(int m, int n) {
        //思路：设dp[i][j]为动态数组，表示从(0, 0)开始到(i, j)总共有dp[i][j]条路径
        //而dp[i][j]只能从两个方向来推导：dp[i - 1][j]和dp[i][j - 1]
        //初始化dp[i][j]数组：从(0, 0)开始到(i, 0)或(0, j)的方法只有一个
        
        //初始化dp数组
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for(int i = 0;i < m; i++){
            dp[i][0] = 1;
        }

        for(int j = 0; j < n;j++){
            dp[0][j] = 1;
        }

        //遍历整个m*n网格
        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
};

63. 不同路径 II（C++动态规划实现）

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
38
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        //思路：首先对于(i, 0)和(0, j)的处理与没有障碍物的题目类似，但是不同的地方在于：
        //由于存在障碍物，需要判断是否等于0，如果等于0，那么设置为1，否则从等于1的地方开始向后都设置为0
        //在更新dp数组的时候需要注意：如果(i, j)有障碍物，那么跳过即可
        //得到行列数
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();

        //初始化dp表
        vector<vector<int>> dp(m, vector<int>(n, 0));

        //初始化最左边的列，障碍物之后都是0
        for(int i = 0;i < m && obstacleGrid[i][0] == 0;i++){
            dp[i][0] = 1;
        }
        
        //初始化最上边的行，障碍物之后都是0
        for(int j = 0;j < n && obstacleGrid[0][j] == 0;j++){
            dp[0][j] = 1;
        }

        //然后更新dp表
        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
                //表示有障碍物
                if(obstacleGrid[i][j] == 1){
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];

    }
};

343. 整数拆分（C++动态规划实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int integerBreak(int n) {
        //思路：dp[i]表示拆分数字i得到的正整数的最大乘积为dp[i]
        //此时，dp[i]可以由如下两种方法得到：
        //1.由j * (i - j)得到；
        //2.由j * dp[i - j]得到，相当于，拆分了dp[i - j]；

        //初始化dp数组
        vector<int> dp(n + 1);
        //初始化dp[2] = 1
        dp[2] = 1; //2 = 1 * 1
        //更新dp数组
        for(int i = 3;i <= n;i++){
            //j实际上从1增加到i / 2即可
            for(int j = 1;j <= i / 2;j++){
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
            }
        }

        return dp[n];
    }
};

96. 不同的二叉搜索树（C++动态规划实现）

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
class Solution {
public:
    int numTrees(int n) {
        //思路：
        //节点数为1的，只有一种；
        //结点数为2的，有两种；

        //节点数为3的，需要分情况讨论：
        //1.头节点为1对应的种类数=右子树有2个结点的种类数*左子树有0个结点的种类数；
        //2.头节点为2对应的种类数=右子树有1个结点的种类数*左子树有1个结点的种类数；
        //3.头结点为3对应的种类数=右子树有0个结点的种类数*左子树有2个结点的种类数；
        //那么节点数为3对应的种类=头节点为1对应的种类数+头节点为2对应的种类数+头节点为3对应的种类数

        //而：0个结点的种类数为dp[0] = 1;
        //有1个结点的种类数为dp[1] = 2;
        //有2个节点的种类数为dp[2] = 2;

        //那么得到递推公式为：dp[3] = dp[2] * dp[0] + dp[0] * dp[2] + dp[1] * dp[1];

        //定义初始化数组：
        vector<int> dp(n + 1);
        //初始化dp[0]为1;
        dp[0] = 1;

        for(int i = 1; i <= n;i++){
            for(int j = 1;j <= i;j++){
                //j从1开始遍历到i结束
                //更新dp动态数组
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        
        return dp[n];
    }
};

01背包问题基础公式推导（C++动态规划实现）

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
38
39
class Solution{
public:
    //背包问题公式推导
    void test_beibao_problem(){
        //设置测试用例
        vector<int> weights = {1, 3, 4};
        vector<int> values = {15, 20, 30};

        //定义背包的最大容量
        int bagweight = 4;

        //定义二维数组
        //第一个维度表示物品数组的长度
        //第二个维度表示背包容量的长度
        vector<vector<int>> dp(weights.size(), vector<int>(bagweight + 1, 0));

        //初始化数组
        //初始化的时候需要注意：从weights开始，小于背包容量的设置为values[0]
        for(int j = weights[0];j <= bagweight;j++){
            dp[0][j] = values[0];//初始化为values[0]
        }

        //先循环物品数组，再循环背包容量数组
        for(int i = 0;i < weights.size();i++){
            //循环背包容量数组
            for(int j = 0;j <= bagweights;j++){
                //如果物品的重量大于j，表示无法将第i个物品放到背包里
                if(j < weights[i]){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
                }
            }
        }

        return dp[weights.size() - 1][bagweights];

    }
}
#Alibaba #LeetCode #C++ #动态规划（dp）算法章节
leetcode-notes-20230915
https://thewangyang.github.io/2023/09/15/leetcode-notes-20230915/
Author
wyy
Posted on
2023年9月15日
Updated on
2023年9月16日
Licensed under