动态规划相关(一)

请注意,本文编写于 460 天前,最后修改于 460 天前,其中某些信息可能已经过时。

LeetCode 53. 最大子序和

题目

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

进阶:
如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

思路

因为是找连续子数组,因此,用dp[i]来存储以第i个数字为结尾的最大子序列,而dp[i] = max(dp[i-1]+Arr[i], Arr[i])

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size()==0) {
            return 0;
        }
        int n = nums.size();
        int dp[n];
        int maxnum = dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i] = INT_MIN;
            dp[i] = max(dp[i-1]+nums[i], nums[i]);
            maxnum = dp[i] > maxnum ? dp[i] : maxnum;
        }
        return maxnum;
    }
};

LeetCode 62. 不同路径

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
问总共有多少条不同的路径?
 

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。

  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3
输出: 28

 

提示:

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9

思路

用数组dpi来存储到达gridi的路径,而dp[i][j] = dp[i-1][j] + dp[i][j-1],边界情况只需加其中一种即可,而dp[0][0] = 1

代码

class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m==0 || n==0) {
            return 0;
        }
        int dp[n][m];
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i==0&&j==0) {
                    continue;
                }
                dp[i][j] = 0;
                if (i==0) {
                    dp[i][j] = dp[i][j-1];
                }else if (j==0) {
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i][j-1] + dp[i-1][j];
                }
            }
        }
        return dp[n-1][m-1];
        
    }
};

LeetCode 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 条不同的路径:

  1. 向右 -> 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右 -> 向右

思路

和上一题一样,只要要考虑一下障碍物情况即可。

代码

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size();
        int m = obstacleGrid[0].size();
        long dp[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (obstacleGrid[i][j]==0) {
                    if (i==0&&j==0) {
                        dp[i][j] = 1;
                        continue;
                    }
                    dp[i][j] = 0;
                    if (i==0) {
                        dp[i][j] = dp[i][j-1];
                    }else if (j==0) {
                        dp[i][j] = dp[i-1][j];
                    }else{
                        dp[i][j] = dp[i][j-1] + dp[i-1][j];
                    }
                }else{
                    dp[i][j] = 0;
                }
            }
        }
        return dp[n-1][m-1];
    }
};

LeetCode 64. 最小路径和

题目

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

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

示例:

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

思路

用dpi来存储到达gridi的最小路径总和,而dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j],再考虑一下边界情况即可。

代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int dp[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i][j] = 0;
                if (i==0&&j==0) {
                    dp[i][j] = grid[i][j];
                    continue;
                }
                if (i==0) {
                    dp[i][j] = dp[i][j-1] + grid[i][j];
                }else if (j==0){
                    dp[i][j] = dp[i-1][j] + grid[i][j];
                }else{
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
                }
            }
        }
        return dp[n-1][m-1];
        
    }
};

此处评论已关闭