LintCode:最小パスと
最小パスと
非負の整数のみを含むm*nメッシュを指定し、左上から右下に数字と最小のパスを見つけます.
LintCode:最小パスと
構想一:万能の列挙 m行、n列の行列、左上から右下に進むには、(m-1)ステップを下に移動し、(n-1)ステップを右に移動し、(m+n-2)ステップを合計すると、パスの総数はC(m+n-2、m-1)ステップとなる. m,nは小さい場合に実行可能であり,大きい場合には実行不可能である.
構想二:動的計画 dp[i][j]は、左上からgrid[i][j]に到達する最小値を表す. dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + a[i][j] 上からdp[i-1][j]+grid[i][j] 左からdp[i][j-1]+grid[i][j] 初期値 dp[0][0] = grid[0][0] dp[0][j>0] = dp[0][j-1] + grid[0][j] dp[i>0][0] = dp[i-1][0] + grid[i][0]
複雑度:時間O(m*n)、空間O(m*n)
dp空間最適化 dp[i][j]はdp[i-1][j]、dp[i][j-1]のみに関連する 対i毎に、順方向ループj 前のdp[j-1]が新しいのか、dp[j]が古いのか dp[j]=min(dp[j-1],dp[j]+a[i][j]更新 空間複雑度O(n)、時間複雑度O(m*n)
参考資料
七月アルゴリズム公開授業実戦動態計画
非負の整数のみを含むm*nメッシュを指定し、左上から右下に数字と最小のパスを見つけます.
LintCode:最小パスと
構想一:万能の列挙
構想二:動的計画
class Solution {
public:
/** * @param grid: a list of lists of integers. * @return: An integer, minimizes the sum of all numbers along its path */
int minPathSum(vector<vector<int> > &grid) {
// write your code here
int m = grid.size();
int n = grid[0].size();
vector<vector<int> > dp(m, vector<int>(n));
for (int i=0; i<m; i++){
for (int j=0; j<n; j++){
if (i==0){
if(j==0){
dp[i][j] = grid[i][j];
}
else{
dp[i][j] = dp[i][j-1] + grid[i][j];
}
}
else if(j==0){
dp[i][j] = dp[i-1][j] + grid[i][j];
}
else{
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
}
return dp[m-1][n-1];
}
};
dp空間最適化
class Solution {
public:
/** * @param grid: a list of lists of integers. * @return: An integer, minimizes the sum of all numbers along its path */
int minPathSum(vector<vector<int> > &grid) {
// write your code here
int m = grid.size();
int n = grid[0].size();
vector<int > dp(n);
for (int i=0; i<m; i++){
for (int j=0; j<n; j++){
if (i==0){
if(j==0){
dp[j] = grid[i][j];
}
else{
dp[j] = dp[j-1] + grid[i][j];
}
}
else if(j==0){
dp[j] = dp[j] + grid[i][j];
}
else{
dp[j] = min(dp[j-1], dp[j]) + grid[i][j];
}
}
}
return dp[n-1];
}
};
参考資料
七月アルゴリズム公開授業実戦動態計画