题目描述：
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。 示例: 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
刚看到，这个题目应该想到的是深搜dfs,但是对于深度优先搜索需要用到递归，对于数据量很大的二维数组来说，时间复杂度过高，今天分享一个新的做法 --- 动态规划
代码：
#include<iostream> #include<stdio.h> #include<string.h> #include<vector> using namespace std; int main() { vector<vector<int> > vec; int row,column; cin >> row >> column; vec.resize(row); for(int i = 0 ; i < row ; i++){ vec[i].resize(column); } for(int i = 0 ; i < row ; i ++) { for(int j = 0 ; j < column ; j ++) { cin >> vec[i][j]; } } int dp[2000][2000]; dp[0][0] = vec[0][0]; for(int i = 0 ; i < row; i ++) { for(int j = 0 ; j < column ; j ++) { if(i == 0 && j == 0) dp[i][j] = vec[i][j]; else if(i == 0 && j>0){ dp[0][j] = dp[0][j-1] + vec[0][j]; } else if(j == 0 && i > 0) { dp[i][0] = dp[i][0] + vec[i][0]; } else if (i> 0 && j > 0){ dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + vec[i][j]; } } } cout << dp[row-1][column-1] << endl; //for(int i = 0 ; i < row ; i ++) //{ // for( int j = 0 ; j < column ; j ++) // { // cout << dp[i][j] << " "; // } // cout << endl; //} return 0; }
总结一下：
1：题目中规定，从原点开始，只能向右或向下走，所以当 i= 0时（i为行） ， 第一行所有的数字和都是由原点一步一步向右 走到的（因为第一行的所有值只能由原点走到，所以就是最小值）， 而 j = 0 时（j 为列）， 第一列所有的数字和都是 从原点向下一步一步 走到的（同理行）， 于是定义一个 dp[row][column] 用来储存 走到 第 i 行 第 j 列 的路径最小和。
2：但是当走到的这个路径既不在第一行也不在第一列上， 记住你之所以走到这个点上，来源只有两个方向，要么是从上而来，要么是从左而来，所以为了使和最小，就要选择这两个中最小的和 再加上 所在路径的数字即可。
让我感觉到动态规划的思想是 之所以你在这个位置 都是 和之前有影响的 ， 每一步都由前一步组成。
状态转移方程式：
- 当 i>0 且 j=0 时，dp[i][0]=dp[i−1][0]+grid[i][0]
- 当 i=0 且 j>0 时，dp[0][j]=dp[0][j−1]+grid[0][j]
- 当 i>0 且 j>0 时，dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:[ [1,3,1], [1,5,1], [4,2,1]]输出: 7解释: 因为路径 1→3→1→1→1 的总和最小。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/minimum-path-sum著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。