路径和(medium)"/>
[dp]leetcode64:最小路径和(medium)
题目:
题解:
- 本题是动态规划的经典好题,状态方程也比较简单。
- dp[i][j]表示原点坐标达到点[i,j]的最小路径和权值,状态转移方程:
dp[i][j]=min(dp[i][j-1],dp[i-1][j])+grid[i][j];
代码如下:
class Solution {
public://题解:动态规划,dp[i][j]表示到达点[i,j]的最小路径和//注意这题不是贪心算法,因为这里取左上两点的最小值是全局最优的,不是局部最优的int minPathSum(vector<vector<int>>& grid) {int n=grid.size(),m=grid[0].size();int dp[n][m];memset(dp,0,sizeof(dp));dp[0][0]=grid[0][0];for(int i=1;i<n;++i){//处理第一列的路径权值和dp[i][0]=dp[i-1][0]+grid[i][0];}for(int i=1;i<m;++i){//处理第一行的路径权值和dp[0][i]=dp[0][i-1]+grid[0][i];}for(int i=1;i<n;++i){//处理除去边界的路径权值和for(int j=1;j<m;++j){dp[i][j]=min(dp[i][j-1],dp[i-1][j])+grid[i][j];}}return dp[n-1][m-1];}
};
更多推荐
[dp]leetcode64:最小路径和(medium)
发布评论