Leecode---多维动态规划---不同路径 / 最小路径和

本文主要是介绍Leecode---多维动态规划---不同路径 / 最小路径和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述
动态规划—三部曲：
1、确定dp数组以及下标含义
dp[i][j]：表示从（0,0）出发，到（i,j）有dp[i][j]条不同的路径
2、确定递推公式
dp[i][j] = dp[i-1][j] + dp[i][j-1]
3、dp数组的初始化
如何初始化，dp[i][0]一定都是1，因为从（0,0）到（0,i）的路径只有一条，dp[0][j]同理：

for (int i = 0; i<m; i++) dp[i][0] = 1;
for (int j = 0; j<n; j++) dp[0][j] = 1;

知识点补充：二维容器vector< vector > 初始化方法解析：

vector<vector<int>> table(size1, vector<int>(size2, 0));

代码说明：声明一个名为table的容器，其元素为vector的容器。简单来说类似一个int型的二维数组。
这样，就得到了一个如下图所示的二维容器。
在这里插入图片描述
理解如下：

图中，将外围容器table的初始化参数分成了两部分A、B。
A: table外围容器的大小
B: table外围容器的内容，即size1个vector型的元素。
B1：内部容器的大小
B2：内部容器的内容

同理：三维容器初始化：
定义一个长宽高为2x3x5的立方体容器，每个元素为0：

//长宽高：2*3*5 vector<vector<vector<int>>> cube(5, vector<vector<int>>(3, vector<int>(2, 0)));

C++代码如下：

class Solution
{
public:int uniquePaths(int m, int n){// 声明一个名为dp的容器，其元素为vector的容器，类似一个int型的二维数组。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;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];}
};

解法二、深搜（超时但同样容易理解）
机器人走过的路径可以抽象为一棵二叉树，而叶子节点就是终点！
在这里插入图片描述
此时问题就可以转化为求二叉树叶子节点的个数，代码如下：

class Solution
{
private:int dfs(int i, int j, int m, int n){if(i>m || j>n) return 0;	//越界if(i == m && j == n) return 1;	// 找到一种方法，相当于找到了叶子节点return dfs(i+1, j, m, n) + dfs(i, j+1, m, n);}
public:int uniquePaths(int m, int n){return dfs(1,1,m,n);}
};

在这里插入图片描述
动态规划—三部曲：
1、确定dp数组以及下标含义
dp(i,j)：表示从（0,0）出发，到（i,j）的最小路径和
2、确定递推公式（转移方程）
左位置和上位置的最短路径和的最小值，加上当前位置的值：
dp(i,j) = min{dp(i-1,j), dp(i,j-1)} + arr[i][j]
3、dp数组的初始化
最左一列和第一行的所有位置都必须作为初始值，防止递推越界。
dp(0,j) = dp(0, j-1) + arr[0][j]
dp(i,0) = dp(i-1, 0) + arr[i][0]
返回值：返回数组右下角的值dp(m-1, n-1)

class Solution
{
public:int minPathSum(vector<vector<int>>& grid){int row = grid.size();int col = grid[0].size();// 初始化for(int i = 1; i<row; i++)grid[i][0] += grid[i-1][0];for(int j = 1; j<col; j++)grid[0][j] += grid[0][j-1];// dp 过程for(int i = 1; i<row; i++){for(int j = 1; j<col; j++){grid[i][j] += min(grid[i-1][j], grid[i][j-1]); }}return grid[row-1][col-1];}
};