Given an m x n grid filled with nonnegative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
动态规划问题．
- 状态转移公式:
F[i,j] = min(F[i,j-1], F[i-1,j]) + A[i,j] - 最优子结构:
F[i,j-1], F[i-1,j] 和 A[i,j] - 边界:
F[0,0] = A[0,0];
参照例子：
1 2 3 4
4 3 2 1
2 1 2 3
实现中有三种选择：
- 最优的: \(O(m*n)\) time, \(O(min(m, n))\) extra space;(maintain an array)
- 次优的: \(O(m*n)\) time, \(O(m)+O(n)\) extra space;(维护俩数组，长度分别m, n)
- 最差的: \(O(m*n)\) time, \(O(m*n)\) extra space.(maintain a matrix, m*n)
自个想法，自个最优空间复杂度代码：
\(O(m*n)\) time, \(O(min(m, n))\) extra space;
// method 2
// DP
// F[i,j] = min(F[i,j-1], F[i-1,j] + A[i,j])
// O(m*n) time, O(min(m,n)) extra space
int minPathSum(vector<vector<int>>& A) {
const int m = A.size(), n = A[0].size();
if (m == 0) return 0;
if (m == 1 && n == 1) return A[0][0];
vector<int> dp(n);
// load the 0st row of A into dp
dp[0] = A[0][0];
for (int j = 1; j < n; j++)
dp[j] = A[0][j] + dp[j - 1];
// fill none first row and col in dp by state transfer equation
for (int i = 1; i < m; i++) {
for (int j = 0; j < n; j++) {
if (j == 0) dp[j] = dp[j] + A[i][0];
else dp[j] = min(dp[j - 1], dp[j]) + A[i][j];
}
}
return dp[n - 1];
}
自个想法，自个差空间复杂度代码：
\(O(m*n)\) time, \(O(m*n)\) extra space;
// method 1
// DP
// F[i,j] = min(F[i,j-1], F[i-1,j]) + A[i,j]
// O(m*n) time, O(m*n) extra space
// not good
int minPathSum(vector<vector<int>>& A) {
const int m = A.size(), n = A[0].size();
if (m == 0) return 0;
if (m == 1 && n == 1) return A[0][0];
// initialize dp(m*n) matrix
vector < vector<int> > dp(m);
for (int i = 0; i < m; i++)
dp[i].resize(n);
// fill first row in dp
dp[0][0] = A[0][0];
for (int j = 1; j < n; j++)
dp[0][j] = A[0][j] + dp[0][j - 1];
// fill first col in dp
for (int i = 1; i < m; i++)
dp[i][0] = A[i][0] + dp[i - 1][0];
// fill none first row and col in dp by state transfer equation
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + A[i][j];
}
}
return dp[m - 1][n - 1];
}
随机推荐
-
treeMap and treeSet
TreeSet:如果要对对象进行排序,对象类要实现Comparable接口! TreeMap:如果要对对象进行排序,对象类要实现Comparable接口! 下面是我自己写的小程序主要传输对象 publ ...
-
poj1988
知道了并查集写的问题后,我也明白了为什么之前这道题TLE的原因: 有这道题的合并操作不难想到用并查集维护: 由于并查集易于向上查询而不易于向下查询 所以对于询问方块x下面有多少个方块,我们可以转化为立 ...
-
c 计算Fibonacci数列：1，1，2，3，5，8，13……这题也是很经典。
输出数字序列2/,/,/,/,/,/...,输出个数由键盘输入.注意输入使用scanf输入 比如: 输入 3输出为 / / / 输入 输出为 / / / / #include<stdio.h&g ...
-
1.javascript节点的操作 创建、添加、移除、移动、复制、插入（修改）
(1)创建新节点 createDocumentFragment() //创建一个DOM片段 createElement() //创建一个具体的元素 createTextNode() //创建一个文本节 ...
-
解决 warning I tensorflow/core/platform/cpu_feature_guard.cc:141] Your CPU supports instructions that this TensorFlow binary was not compiled to use: AVX2
只需要加载如下代码: import os os.environ['
-
ubuntu安装jdk8
文章连接:https://www.cnblogs.com/lighten/p/6105463.html 1.简单的安装方法 安装JDK的最简单方法应该就是使用apt-get来安装了,但是源一般是Ope ...
-
Kali proxychains
1.什么是proxychains 在linux系统中有很多软件是不支持代理的,但是proxychains 却可以让不支持代理的软件 也能走代理通道,支持HTTP,HTTPS,SOCKS4,SOCKS5 ...
-
sqlalchemy 使用pymysql连接mysql 1366错误
一.错误情况 mysql 5.7.2 \python35\lib\site-packages\pymysql\cursors.py:166: Warning: (1366, "Incorre ...
-
tp框架中的一些疑点知识--cookie和session的配置
不同的浏览器采用不同的方式保存Cookie. IE浏览器会在"C:\Documents and Settings\你的用户名\Cookies"文件夹下以文本文件形式保存,一个文本文 ...
-
【HNOI2015】实验比较
题面 题解 首先将所有相等的用并查集缩点,然后会发现题目有一个很有用的性质: 对每张图片\(i\),小D都最多只记住了某一张质量不比\(i\)差的另一张图片\(K_i\). 于是将\(K_i\)作为\ ...