|
題目：給定一個(gè)矩陣，從左上角開(kāi)始每次只能向右或者向下移動(dòng)，最后到達(dá)右下角的位置，路徑上的所有的數(shù)字累加起來(lái)作為這條路徑的路勁和。要求返回所有路徑和中的最小路徑和。 舉例：
路徑1,3,1,0,6,1,0是所有路徑中路徑和最小的，所以返回其和12。
解析： 這個(gè)題目很類似之前的那個(gè)動(dòng)態(tài)規(guī)劃的數(shù)字三角的問(wèn)題。毫無(wú)疑問(wèn)的，這個(gè)問(wèn)題也是用動(dòng)態(tài)規(guī)劃解決。只要確定了狀態(tài)和轉(zhuǎn)移方程，這個(gè)題目很容易解決。下面直接給出代碼： //利用path記錄路徑，對(duì)于每一個(gè)path[i][j],0代表dp[i][j]的值從上面加過(guò)來(lái)，1代表dp[i][j]的值從左邊加過(guò)來(lái)
int minPathSum1(int matrix[][col], int dp[][col], int path[][col])
{
if(matrix == NULL)
{
return 0;
}
dp[0][0] = matrix[0][0];
//計(jì)算第一列的值
for(int i = 1; i < row; i ++)
{
dp[i][0] = dp[i - 1][0] + matrix[i][0];
path[i][0] = 0;
}
//計(jì)算第一行的值
for(int j = 1; j < col; j++)
{
dp[0][j] = dp[0][j- 1] + matrix[0][j];
path[0][j] = 1;
}
//計(jì)算其它的值
for(int i = 1; i < row; i++)
{
for(int j = 1; j < col; j++)
{
int direction = dp[i][j-1] < dp[i-1][j] ? 1 : 0;
dp[i][j] = (direction ? dp[i][j-1] : dp[i-1][j]) + matrix[i][j];
path[i][j] = direction;
}
}//for
return dp[row - 1][col - 1];
}
這里在dp上存儲(chǔ)每個(gè)點(diǎn)的最短路徑和，在path上存儲(chǔ)這個(gè)最短路徑是哪個(gè)點(diǎn)過(guò)來(lái)的。這樣就能在找到最短路徑和的同時(shí)，把路徑一塊找到。 二維動(dòng)態(tài)規(guī)劃的空間壓縮上面的題目很簡(jiǎn)單，不是這篇文章的重點(diǎn)，下面來(lái)看一下二維動(dòng)態(tài)規(guī)劃的空間壓縮問(wèn)題。上面的動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度是O(M*N)，空間復(fù)雜度就是二維數(shù)組的大小O(M*N)。空間壓縮的方法是不用記錄所有的子問(wèn)題的解。所以就可以只用一個(gè)行數(shù)組記錄第一行、第二行...一次計(jì)算。直到最后一行，得到dp[N-1]就是左上角到右下角的最小路徑和。 代碼實(shí)現(xiàn)： int minPathSum2(int matrix[][col], int dp[])
{
dp[0] = matrix[0][0];
//計(jì)算第一行的最短路徑
for(int j = 1; j < col; j++)
{
dp[j] = dp[j-1] + matrix[0][j];
}
//計(jì)算除了第一行的其它最小路徑和
for(int i = 1; i < row; i++)
{
for(int j = 0; j < col; j++)
{
if(j == 0)
{
dp[j] += matrix[i][j];
}
else
{
dp[j] = dp[j-1] < dp[j] ? dp[j-1] : dp[j];
dp[j] += matrix[i][j];
}
}//for
}//for
return dp[col - 1];
}
這種二維動(dòng)態(tài)規(guī)劃的空間壓縮幾乎可以應(yīng)用到所有的二維動(dòng)態(tài)規(guī)劃的題目中，通過(guò)一個(gè)數(shù)組（列數(shù)組或者航數(shù)組）滾動(dòng)更新的方式節(jié)省了大量的空間。但是在滾動(dòng)的過(guò)程中動(dòng)態(tài)規(guī)劃表不斷的被行數(shù)組或者列數(shù)組覆蓋更新，最后得到的僅僅是動(dòng)態(tài)規(guī)劃表的最后一行或者最后一列的最小路徑和。所以真正的最小路徑是不能通過(guò)動(dòng)態(tài)規(guī)劃表回溯得到的。矩陣最小路徑和二維動(dòng)劃的空間壓縮 |
|
|
