﻿ 动态规划中初识状态压缩（入门）_其他_开心洋葱网
• 欢迎访问开心洋葱网站，在线教程，推荐使用最新版火狐浏览器和Chrome浏览器访问本网站，欢迎加入开心洋葱` QQ群`
• 为方便开心洋葱网用户，开心洋葱官网已经开启复制功能！
• 欢迎访问开心洋葱网站，手机也能访问哦~欢迎加入开心洋葱多维思维学习平台` QQ群`
• 如果您觉得本站非常有看点，那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~！
• 由于近期流量激增，小站的ECS没能经的起亲们的访问，本站依然没有盈利，如果各位看如果觉着文字不错，还请看官给小站打个赏~~~~~~~~~~~~~！

# 动态规划中初识状态压缩（入门）

2213次浏览

``````public int minPathSum(int[][] grid)
``````

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

``````class Solution {
public int minPathSum(int[][] grid) {
if (grid.length == 0) return 0;
int n = grid.length;
int m = grid[0].length;
int[][] dp = new int[n][m];
dp[0][0] = grid[0][0];
//初始化
//从（0，0）一直向下走
for (int i = 1; i < n; i++)
dp[i][0] = dp[i - 1][0] + grid[i][0];
//从（0，0）一直向右走
for (int j = 1; j < m; j++)
dp[0][j] = dp[0][j - 1] + grid[0][j];

//状态转移
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++)
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
return dp[n - 1][m - 1];
}
}
``````

``````class Solution {
public int minPathSum(int[][] grid) {
if (grid.length == 0) return 0;
int n = grid.length;
int m = grid[0].length;
int[][] dp = new int[n + 1][m + 1];
//初始化
for (int i = 0; i <= n; i++)
dp[i][0] = Integer.MAX_VALUE;
dp[1][1] = grid[0][0];
//初始状态
//从（1，1）一直往右走
for (int j = 2; j <= m; j++)
dp[1][j] = dp[1][j - 1] + grid[0][j - 1];

//状态转移
for (int i = 2; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
return dp[n][m];
}
}
``````

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

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

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

``````class Solution {
public int minPathSum(int[][] grid) {
if (grid.length == 0) return 0;
int n = grid.length;
int m = grid[0].length;
int[] dp = new int[m + 1];
//初始化
dp[0] = Integer.MAX_VALUE;
dp[1] = grid[0][0];
//从（1，1）一直向右走  真的只是把上面的代码中dp[i][j]的i那一维去掉
for (int j = 2; j <= m; j++)
dp[j] = dp[j - 1] + grid[0][j - 1];
//这里也是直接去掉i中的那一维
for (int i = 2; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i - 1][j - 1];
return dp[m];
}
}
``````

• 版权声明

本站的文章和资源来自互联网或者站长
的原创，按照 CC BY -NC -SA 3.0 CN
协议发布和共享，转载或引用本站文章
应遵循相同协议。如果有侵犯版权的资
源请尽快联系站长，我们会在24h内删
除有争议的资源。
• 合作网站

• 友情链接

• 关于我们

一群热爱思考，热爱生活，有理想的新社会主义接班人的多维思维学习平台，天行健，君子以自强不息。地势坤，君子以厚德载物。