纯C解决-经典动规之最小路径和，二维动规总结(附c++解决)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了纯C解决-经典动规之最小路径和，二维动规总结(附c++解决)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1960字，纯文字阅读大概需要3分钟。

内容图文

解题思路

对于二维动态规划，这种题是非常常见的了，只要明白基本套路就很容易了，非常类似的，换汤不换药的，我这里总结了LeetCode几道题：
地牢游戏
不同路径
不同路径II
杨辉三角

• 此处讲解的便是本题建议先点进去看题目
  最小路径和
  基本思路都是一样的，接下来我给大家细说，主要分成三步：

1.初始化左上角

2.初始化首行首列

3.利用状态转移方程更新各个节点

举个例子：

1   2

3   4

我们要从左上角到达右下角，对于4只有2 和 3 可以到达，那么如果我们知道了2和3的最小路径和，然后取两者最小不就可以得出到打4的最小路径和了吗？
那么问题就转换成求2 和 3 的最小路径和

故，得出状态转移方程：

dp[i][j] = (dp[i-1][j] < dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]) + grid[i][j];

然后我们紧接着需要考虑一下边界条件，也就是初始化:

1.对于左上角的位置，我们只能直接赋值

2.对于首行，它只能由左边的位置往右前进一步得出

3.对于首列，它只能由上边的位置往下前进一步得出

代码

C语言代码

int minPathSum(int** grid, int gridSize, int* gridColSize){
    if(gridSize==0 || *gridColSize==0) return 0;
    int dp[gridSize][*gridColSize];
    int i,j;
    //初始化
    dp[0][0] = grid[0][0];

    for(i=1;i < gridSize;i++)//初始列
    dp[i][0] = dp[i-1][0] + grid[i][0];

    for(j=1;j < *gridColSize;j++)//初始行
    dp[0][j] = dp[0][j-1] + grid[0][j];

    for(i=1;i < gridSize;i++)
        for(j=1;j < *gridColSize;j++)
        {
            dp[i][j] = (dp[i-1][j] < dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]) + grid[i][j];
        }
    return dp[i-1][j-1];
}

C++代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
    int r = grid.size();//数组的行
    int c = grid[0].size();//数组的列
    vector<vector<int>> dp(r , vector<int>(c,0));//初始化一个dp二维数组用于存储每个位置的最优解

    dp[0][0] = grid[0][0];//(0,0)位置的最优解等于该位置的值
    for(int i = 1;i < c;i++)
        dp[0][i] = dp[0][i-1] + grid[0][i];//初始化首行的最优解
    for(int i = 1;i < r;i++)
        dp[i][0] = dp[i][0] + grid[i][0];//初始化首列的最优解
    for(int i = 1;i < r;i++){
        for(int j = 1;j < c;j++){
//位置(i,j)的最优解等于左侧或者上方位置中较小的值加上该位置的值(一行一行的进行更新或者一列一列的也行))
            dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + grid[i][j];
        }
    }
    return dp.back().back();
    }
};

内容总结

以上是互联网集市为您收集整理的纯C解决-经典动规之最小路径和，二维动规总结(附c++解决)全部内容，希望文章能够帮你解决纯C解决-经典动规之最小路径和，二维动规总结(附c++解决)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端