开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 动态规划2——常考的求路径问题，看不会就记住 -> 正文阅读

[数据结构与算法]动态规划2——常考的求路径问题，看不会就记住

NC34 求路径

https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358?tpId=117&&tqId=37736&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking

一个机器人在m×n大小的地图的左上角（起点）。

机器人每次向下或向右移动。机器人要到达地图的右下角（终点）。

可以有多少种不同的路径从起点走到终点？

思路：

问题：从（0，0）—>(row-1, col-1)的路径个数

状态：(0, 0)—>(i, j)的路径个数

转移方程:F(i, j) = F(i, j-1) + F(i-1, j) 当前点的路径个数等于左边点和上边点的路径个数

初始状态：F(0, j) = F(i, 0) = 1 第一行和第一列都是1

返回：F（row-1， col-1）

代码

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        // write code here
        int dp[m][n];
        for(int j = 0; j < n; ++j)
            dp[0][j] = 1;
        for(int i = 0; i < m; ++i)
            dp[i][0] = 1;
        for(int i = 1; i < m; ++i)
        {
            for(int j = 1; j < n; ++j)
            {
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
        
        return dp[m-1][n-1];
    }
};

NC19 子数组的最大累加和问题

https://www.nowcoder.com/practice/554aa508dd5d4fefbf0f86e5fe953abd?tpId=117&&tqId=37797&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking

描述

给定一个数组arr，返回子数组的最大累加和

例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.

题目保证没有全为负数的数据

[要求]

时间复杂度为O(n)O(n)，空间复杂度为O(1)O(1)

示例1

输入：

[1, -2, 3, 5, -2, 6, -1]

复制

返回值：

思路

状态：长度为i的子数组和的最大值

状态方程：F(i) = max(F(i-1) + arr[i], arr[i]) F(i)的最大值为前一个状态的值+arr[i]的值和当前arr[i]的值取最大

F(i-1) = F(i-1) > 0 ? F(i-1) + arr[i] : arr[i]

初始状态：F(0) = arr[0]

返回值：所有F[i]中的最大值

代码

class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector<int>& arr) {
        // write code here
        vector<int> dp(arr.size(), 0);
        int i = 0;
        dp[0] = arr[0];
        int maxSum = dp[0];
        for(i = 1; i < arr.size(); ++i)
        {
            dp[i] = dp[i - 1] +arr[i] >= arr[i] ? dp[i-1] + arr[i] : arr[i];
            maxSum = max(maxSum, dp[i]);
        }
        
        return maxSum;
    }
};

LC31 三角形

https://www.nowcoder.com/practice/2b7995aa4f7949d99674d975489cb7datpId=46&tqId=29060&tPage=2&rp=2&ru=/ta/leetcode&qru=/ta/leetcode/question-rankin

描述

给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字，

例如，给出的三角形如下：

[[20],[30,40],[60,50,70],[40,10,80,30]]

最小的从顶部到底部的路径和是20 + 30 + 50 + 10 = 110。

注意：如果你能只用O（N）的额外的空间来完成这项工作的话，就可以得到附加分，其中N是三角形中的行总数

思路

状态：从(0, 0)到(i, j)的最小路径，注意每一步只能移到下面一行相邻的数字(i, j)的下一行就是(i+1,j)和(i+1, j+1)，对于(i , j)我们倒推回去即可，但要注意边界，最左边的一行和最右边的一行

状态方程：F(i, j) = min{F(i - 1, j) ，F(i-1, j-1)}

j = 0的话上面只有一个F(i-1, j)

j = i的话上面也只有一个F(i-1, j-1)

初始状态：F(0, 0) = triangle[0][0]

返回值：min(F(n-1, i))

代码

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        if(triangle.empty())
            return 0;
        vector<vector<int>> dp(triangle);
        dp[0][0] = triangle[0][0];
        for(int i = 1; i < triangle.size(); ++i)
        {
            for(int j = 0; j <= i; ++j)
            {
                if(j == 0)
                    dp[i][j] = dp[i-1][j];
                else if(j == i)
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]);
                dp[i][j] = dp[i][j] + triangle[i][j]; //记得加上当前值
            }
           
        }
        int min = INT_MAX;
        for(int i = triangle.size()-1, j = 0; j <= i; ++j)
        {
            if(dp[i][j] < min)
                min = dp[i][j];
            
        }
        
        return min;
    }
};

LC88 求路径

https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358?tpId=46&tqId=29117&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking

描述

一个机器人在m×n大小的地图的左上角（起点）。

机器人每次向下或向右移动。机器人要到达地图的右下角（终点）。

可以有多少种不同的路径从起点走到终点？

思路

状态：子状态：从(0,0)到达(1,0),(1,1),(2,1),…(m-1,n-1)的路径数

? F(i,j): 从(0,0)到达F(i,j)的路径数

状态递推： F(i,j) = F(i-1,j) + F(i,j-1)

初始化：

? 特殊情况：

第0行和第0列
F(0,i) = 1
F(i,0) = 1

返回结果： F(m-1,n-1)

代码

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        // write code here
    vector<vector<int>> dp(m, vector<int>(n, 1));
        for(int i = 1; i < m; ++i)
        {
            for(int j = 1; j < n; ++j)
            {
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
        
        return dp[m-1][n-1];
    }
};

LC87 求路径 ii

https://www.nowcoder.com/practice/3cdf08dd4e974260921b712f0a5c8752?tpId=46&tqId=29116&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking

描述

给定一个m*n的地图，其中加入了一些障碍。每次只能向下或者向右走，问从左上角走到右下角有多少不同的路径？

分别用0和1代表空区域和障碍

例如

下图表示有一个障碍在3*3的图中央。

[
    [0,0,0],
    [0,1,0],
    [0,0,0]
]

有2条不同的路径

思路

状态：

子状态：从(0,0)到达(1,0),(1,1),(2,1),…(m-1,n-1)的路径数

F(i,j): 从(0,0)到达F(i,j)的路径数

状态递推： F(i,j) = {F(i-1,j) + F(i,j-1)} OR {0, if obstacleGrid(i,j) = 1}

初始化：

特殊情况：

第0行和第0列

F(0,i) = {1} OR {0, if obstacleGrid(0,j) = 1, j <= i}

F(i,0) = {1} OR {0, if obstacleGrid(j,0) = 1, j <= i}

返回结果： F(m-1,n-1)

代码

class Solution {
public:
    /**
     * 
     * @param obstacleGrid int整型vector<vector<>> 
     * @return int整型
     */
    int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid) {
        // write code here
        if (obstacleGrid.empty() || obstacleGrid[0].empty()) 
        {
         return 0;
        }

        int row = obstacleGrid.size();
        int col = obstacleGrid[0].size();
        //全0填充当遇到1后break即可
        vector<vector<int>> dp(row, vector<int>(col, 0));
        dp[0][0] = 0;
        
        for(int i = 0; i < row; ++i)
        {
            //遇到障碍物后面都无法到达
            if(obstacleGrid[i][0] == 1)
                break;
            else 
                dp[i][0] = 1;
        }
        for(int j = 0; j < col; ++j)
            //遇到障碍物后面都无法到达
            if(obstacleGrid[0][j] == 1)
                break;
            else 
                dp[0][j] = 1;
        
        
        for(int i = 1; i < row; ++i)
        {
            for(int j = 1; j < col; ++j)
            {
                if(obstacleGrid[i][j] == 1)
                    dp[i][j] = 0;
                else 
                    dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
        
        return dp[row-1][col-1];
    }
};

NC59 矩阵的最小路径和

https://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb?tpId=190&&tqId=35224&rp=1&ru=/activity/oj&qru=/ta/job-code-high-rd/question-ranking

描述

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

示例1

输入：

[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]

复制

返回值：

思路

状态：

子状态：从(0,0)到达(1,0),(1,1),(2,1),…(m-1,n-1)的最短路径

F(i,j): 从(0,0)到达F(i,j)的最短路径

状态递推： F(i,j) = min{F(i-1,j) , F(i,j-1)} + (i,j)

初始化： F(0,0) = (0,0)

特殊情况：

第0行和第0列

F(0,i) = F(0,i-1) + (0,i)

F(i,0) = F(i-1,0) + (i,0)

返回结果： F(m-1,n-1)

代码

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        // write code here
        vector<vector<int>> dp(matrix);
        int row = matrix.size();
        int col = matrix[0].size();

        for(int i = 1; i < row; ++i)
        {
            dp[i][0] = dp[i-1][0] + matrix[i][0];
        }
        for(int j = 0; j < col; ++j)
            dp[0][j] = dp[0][j-1] + matrix[0][j];
        
        for(int i = 1; i < row; ++i)
        {
            for(int j = 1; j < col; ++j)
            {
                dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + matrix[i][j];
            }
        }
        
        return dp[row-1][col-1];
    }
};