Java 动态规划 64. 最小路径和-Toy模板网

这篇具有很好参考价值的文章主要介绍了Java 动态规划 64. 最小路径和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Java 动态规划 64. 最小路径和,动态规划,算法,java

代码展示：

dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];

该题可以通过动态规划解决，动态规划的题根据以下的5大步骤便可轻松解决

1.状态表示

题目要求我们计算从起点到最后一个位置的最小路径和，我们可以创建一个dp表，dp【i】【j】表示从起点到【i，j】位置的最小路径和

2.状态转移方程

我们从最近的一步开始分析，我们有两种方法可以到达【i，j】位置，要么从【i-1，j】位置向下移动，要么从【i，j-1】位置向右移动，我们要如何选择呢，由于我们需要求出的是最小路径和，所以我们可以比较到达【i-1，j】和【i，j-1】的最小路径和，即dp【i-1，j】和dp【i，j-1】,从较小的那个位置出发到【i，j】位置即加上【i，j】位置的数值，便是【i，j】的最小路径和，所以我们可以得到状态转移方程： dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];

3.初始化

我们可以通过增加辅助结点的方式来辅助初始化，在该题中我们创建的dp数值相比于grid数组，我们要多加一行一列，而此时我们要注意，

（1）.辅助结点中添加的值要保证后续的数据添加是正确的，根据对该题的分析，我们需要将第一行和第一列除了[0,1]位置和[1.0]位置，其他位置都设为int数据的最大值

（2）.下标的映射关系，此时由于添加了一行一列，所以dp[i][j]对应grid[i-1][j-1]

4.填充数组

根据状态转移方程填充数组

5，返回值

终点位置是【m，n】,所以要返回dp[m][n]文章来源地址https://www.toymoban.com/news/detail-545668.html

到了这里，关于Java 动态规划 64. 最小路径和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！