煮酒与君饮

这个屌丝很懒，什么也没留下！

热门标签

Leetcode刷题笔记（C++）——动态规划_每次哪吒只能向下或者向右移动一步,每一格有一个正整数k

作者：煮酒与君饮 | 2024-07-30 14:29:04

踩

每次哪吒只能向下或者向右移动一步,每一格有一个正整数k

Leetcode刷题笔记（C++）——动态规划

整理一下刷题过程中的思路，在这里进行一下总结与分享。
github地址：https://github.com/lvjian0706/Leetcode-solutions
github项目是刚刚新建的，陆续会将整理的代码以及思路上传上去，代码是基于C++与python的。同时会将基础的排序算法等也一并进行整理上传。

45. 跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

class Solution {
public:
    /*
    最少跳跃次数：动态规划和贪心算法都可以（贪心比较容易但是思路不好想）
    动态规划：dp数组存放到达该位置的最少跳跃次数；(超出时间限制)
    1. 初始条件：在位置0出发，dp[0]=0；
    2. 状态方程：
    2.1 首先判断从哪些位置可以到达位置n：判断位置n之前的任意一个位置走对应步数是否可以到达位置n，nums[i]>=n-i;
    2.2 查找上述位置中的最小跳跃次数加1即为到位置n的最小跳跃次数：dp[n]=min(dp[*])+1;
    */
    int jump(vector<int>& nums) {
        vector<int> dp(nums.size());
        dp[0]=0;
        int minTimes;
        for(int i=1; i<nums.size(); i++){
            /*
            初始化最小跳跃次数为i，即每次都只跳1步
            */
            minTimes=i;
            for(int j=0; j<i; j++){
                if(nums[j]>=i-j && dp[j]<minTimes) minTimes = dp[j];
            }
            dp[i] = minTimes + 1;
        }
        return dp[nums.size()-1];
    }
};


class Solution {
public:
    /*
    最少跳跃次数：动态规划和贪心算法都可以（贪心比较容易但是思路不好想）
    贪心算法：使用preMax记录目前可以到达的最远位置，使用maxNum记录可以到达的最远位置
    1. preMax和maxNum的初始值设为nums[0],表示第一步能走的最大距离，minJump代表最小跳跃次数，初始化为1；
    2. 循环遍历数组，当i+nums[i]>maxNum时，更新maxNum为i+nums[i]；
    3. 当超过preMax的范围时，更新preMax的值为maxNum，最少跳跃次数加1;
    */
    int jump(vector<int>& nums) {
        /*
        当数组中小于两个元素时，不用跳跃即可到达
        */
        if(nums.size()<2) return 0;
        int preMax=nums[0], maxNum=nums[0];
        int minJump=1;
        for(int i=0; i<nums.size(); i++){
            if(i>preMax){
                minJump++;
                preMax = maxNum;
            }
            if(i+nums[i]>maxNum) maxNum=i+nums[i];
        }
        return minJump;
    }
};


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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

55. 跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ，所以你永远不可能到达最后一个位置。

class Solution {
public:
    /*
    是否能够到达：动态规划和贪心算法都可以（贪心比较容易但是思路不好想）
    动态规划：dp数组存放能否到达该位置，0：不可以1：可以；
    1. 初始条件：在位置0出发，所以一定可以到达位置0，dp[0]=1；
    2. 状态方程：判断是否可以到达位置n之前的任意一个位置，且在该位置走对应步数可以到达位置n，如果存在则可以到达该位置，dp[n]=dp[i]&&nums[i]>=n-i;
    */
    bool canJump(vector<int>& nums) {
        vector<int> dp(nums.size());
        dp[0]=1;
        for(int i=1; i<nums.size(); i++){
            for(int j=0; j<i; j++){
                if(dp[j]&&nums[j]>=i-j){
                    dp[i] = 1;
                    break;
                }
            }
        }
        return dp[nums.size()-1];
    }
};

class Solution {
public:
    /*
    是否能够到达：动态规划和贪心算法都可以（贪心比较容易但是思路不好想）
    贪心算法：使用maxNum记录当前可以到达的最远位置
    1. maxNum<i时，代表当前可以到达的最远位置比i小，因此无法到达i，返回false
    2. (i+nums[i])>maxNums时，代表在位置i可以到达比maxNums更远的位置，更新maxNums
    */
    bool canJump(vector<int>& nums) {
        int maxNums = 0;
        for(int i=0; i<nums.size(); i++){
            if(maxNums<i) return false;
            if((i+nums[i])>maxNums) maxNums = i+nums[i];
        }
        return true;
    }
};
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
40

62. 不同路径

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

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

问总共有多少条不同的路径？
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。

向右 -> 向右 -> 向下
向右 -> 向下 -> 向右
向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28

class Solution {
public:
    /*
    动态规划问题：新建dp数组存储到达该点的路径数
    1. 初始状态：由于只能只能向下或者向右移动，dp数组第一列和第一行元素均为1：
    2. 状态方程：dp[i][j] = dp[i-1][j]+dp[i][j-1];
    3. 因为想走到右下角，所以返回答案为dp[m-1][n-1];
    */
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n));
        dp[0][0] = 1;
        for(int i=0; i<m; i++){
            dp[i][0] = 1;
        } 
        for(int i=0; i<n; i++){
            dp[0][i] = 1;
        }
        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];
    }
};
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

63. 不同路径 II

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

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：

向右 -> 向右 -> 向下 -> 向下
向下 -> 向下 -> 向右 -> 向右

class Solution {
public:
    /*
    动态规划问题：新建dp数组存储到达该点的路径数
    1. 初始状态：由于只能只能向下或者向右移动，dp数组第一列和第一行元素均为1，
    （其中，考虑到如果有障碍，从该点往后的所有点都无法到达，因此，定义flag变量，碰到障碍则flag=1，dp数组从该点开始全都赋0）
    2. 状态方程：dp[i][j] = dp[i-1][j]+dp[i][j-1];
    （其中，考虑到如果有障碍，到障碍点的路径数应该设置为0，表明该点不通且无法到达）
    3. 因为想走到右下角，所以返回答案为dp[m-1][n-1];
    */
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n));
        int flag = 0;
        for(int i=0; i<m; i++){
            if(obstacleGrid[i][0]==1){
                flag = 1;
            }
            if(!flag) dp[i][0] = 1;
            else dp[i][0] = 0;
        }
        flag = 0;
        for(int i=0; i<n; i++){
            if(obstacleGrid[0][i]==1){
                flag = 1;
            }
            if(!flag) dp[0][i] = 1;
            else dp[0][i] = 0;
        }
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(obstacleGrid[i][j]==1) dp[i][j] = 0;
                else dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
        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
38
39

64. 最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

class Solution {
public:
    /*
    动态规划问题：新建dp数组存储路径上的最小数字和
    1. 初始状态：由于只能只能向下或者向右移动，dp数组第一列和第一行元素计算方式：
    1.1 dp数组第一列的元素计算方式为dp[i][0] = dp[i-1][0] + grid[i][0];
    1.2 dp数组第一行的元素计算方式为dp[0][i] = dp[0][i-1] + grid[0][i];
    2. 状态方程：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
    3. 因为想走到右下角，所以返回答案为dp[m-1][n-1];
    */
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n));
        dp[0][0] = grid[0][0];
        for(int i=1; i<m; i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int i=1; i<n; i++){
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        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

70. 爬楼梯

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

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

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

示例 1：
输入： 2
输出： 2
解释：有两种方法可以爬到楼顶。

1 阶 + 1 阶
2 阶
示例 2：
输入： 3
输出： 3
解释：有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶

class Solution {
public:
    /*
    求可行个数：动态规划
    1. 初始条件：爬到0层有1种方法，爬到1层有1种方法（爬1阶），dp[0]=1，dp[1]=1,;
    2. 状态方程：爬到第n层可以在n-1层爬1阶，也可以在n-2层爬2阶，因此dp[n]=dp[n-1]+dp[n-2];
    */
    int climbStairs(int n) {
        if(n==0) return 1;
       vector<int> dp(n+1);
       dp[0] = 1, dp[1] = 1;
       for(int i=2;i<n+1;i++){
           dp[i] = dp[i-1] + dp[i-2];
       }
       return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

120. 三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。

例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

class Solution {
public:
    /*
    动态规划问题，建立dp数组；
    由于是三角形，求自顶向下的最小路径和，为了计算方便，适合从下向上计算，最后dp[0][0]即为最终答案；
    1. 初始状态：dp数组的每一个值代表从下向上的最小路径和，其中，dp数组最后一行为原始三角形中最下一行元素；
    2. 状态方程：dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1]);
    */
    int minimumTotal(vector<vector<int>>& triangle) {
        /*
        三角形最后一行索引以及三角形最后一行长度
        */
        int lastRaw = triangle.size(), maxLen = triangle[triangle.size()-1].size();
        vector<vector<int>> dp(lastRaw, vector<int>(maxLen));
        for(int i=0; i<maxLen; i++){
            dp[lastRaw-1][i] = triangle[lastRaw-1][i];
        }
        /*
        从倒数第二行开始往上计算，每行的数组元素个数比下边一行少1；
        */
        for(int i=lastRaw-2; i>=0; i--){
            maxLen--;
            for(int j=0; j<maxLen; j++){
                dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1]);
            }
        }
        return dp[0][0];
    }
};
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

300. 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。

class Solution {
public:
    /*
    要求最长上升子序列的长度：动态规划，dp数组存放最长上升子序列的长度
    1. 初始状态：每个位置上升子序列的长度最少为1（元素本身），因此，dp数组所有元素初始化为1；
    2. 状态方程：求解以每个位置元素为最后一个元素的最长上升子序列的长度，首先判断之前元素中小于该元素的位置，再找到dp数组中这些位置的最大值，dp[i]=max(dp[*])+1；
    3. 返回值：dp数组的最大值；
    */
    int lengthOfLIS(vector<int>& nums) {
        /*
        数组为空时，返回0；
        */
        if(nums.size()==0) return 0;
        vector<int> dp(nums.size(), 1);
        int maxLen;
        for(int i=0; i<nums.size(); i++){
            maxLen = dp[i];
            for(int j=0; j<i; j++){
                if(nums[j]<nums[i] && dp[j]+1>maxLen) maxLen=dp[j]+1;
            }
            dp[i] = maxLen;
        }
        int ans = dp[0];
        for(int i=1; i<dp.size(); i++){
            if(dp[i]>ans) ans = dp[i];
        }
        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
26
27
28
29

322. 零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1

说明:
你可以认为每种硬币的数量是无限的。

class Solution {
public:
    /*
    最少的组合个数：动态规划问题，dp数组中存放凑成金额i所需要的最少硬币个数
    1. 初始状态：初始状态时，默认除了0之外所有面额都不能凑成，都赋值为-1，面额为0时，可使用0枚硬币凑成，因此，dp[0]=0；
    2. 状态方程：面额i可以根据dp[i-coins[j]]的最小值加1凑成，因此，dp[i]]=min(dp[i-coins[j]])+1；(其中，需要判断边界值i>=coins[j]以及dp[i-coins[j]]!=-1即面额i是否可以用coins中的硬币凑成)
    3. 返回值：dp[amount]
    */
    int coinChange(vector<int>& coins, int amount) {
        /*
        如果没有硬币，返回-1；
        */
        if(coins.size()==0) return -1;
        vector<int> dp(amount+1, -1);
        dp[0] =  0;
        for(int i=1; i<amount+1; i++){
            for(int j=0; j<coins.size(); j++){
                if(i>=coins[j] && dp[i-coins[j]]!=-1){
                    if(dp[i]==-1) dp[i] =  dp[i-coins[j]] + 1;
                    else dp[i] = min(dp[i], dp[i-coins[j]] + 1);
                }
            }
        }
        return dp[amount];
    }
};
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

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:
输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace”，它的长度为 3。
示例 2:
输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc”，它的长度为 3。
示例 3:
输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0。
提示:
1 <= text1.length <= 1000
1 <= text2.length <= 1000
输入的字符串只含有小写英文字符。

class Solution {
public:
    /*
    最长公共子序列的长度：动态规划问题，dp数组存放text1[0:i]与text2[0:j]的最长公共子序列的长度（二维数组）
    1. 初始状态：当text1[0:i]中有元素与text2[0]相等时，dp[i][0]=1；当text2[0:j]中有元素与text1[0]相等时，dp[0][j]=1；
    2. 状态方程：
    2.1 当text1[i]==text2[j]时，dp[i][j] = dp[i-1][j-1]+1;
    2.2 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    3. 返回值：dp[text1.size()-1][text2.size()-1]
    */
    int longestCommonSubsequence(string text1, string text2) {
        int m=text1.length(), n=text2.length();
        vector<vector<int>> dp(m, vector<int>(n));
        int flag = 0;
        for(int i=0; i<m; i++){
            if(text1[i]==text2[0]) flag=1;
            if(flag) dp[i][0]=1;
            else dp[i][0]=0;
        }
        flag = 0;
        for(int j=0; j<n; j++){
            if(text2[j]==text1[0]) flag=1;
            if(flag) dp[0][j]=1;
            else dp[0][j]=0;
        }
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(text1[i]==text2[j]) dp[i][j] = dp[i-1][j-1]+1;
                else dp[i][j] =  max(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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/904094