本專欄內(nèi)容為：算法學(xué)習(xí)專欄，分為優(yōu)選算法專欄，貪心算法專欄，動態(tài)規(guī)劃專欄以及遞歸，搜索與回溯算法專欄四部分。 通過本專欄的深入學(xué)習(xí)，你可以了解并掌握算法。
??博主csdn個(gè)人主頁：小小unicorn
?專欄分類：動態(tài)規(guī)劃專欄
??代碼倉庫：小小unicorn的代碼倉庫??
??????關(guān)注我?guī)銓W(xué)習(xí)編程知識
題目來源
本題來源為：
Leetcode62. 不同路徑
題目描述
一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為 “Start” ）。
機(jī)器人每次只能向下或者向右移動一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為 “Finish” ）。
問總共有多少條不同的路徑？
題目解析
我們可以模擬一下機(jī)器人的過程：
算法原理
1.狀態(tài)表示
經(jīng)驗(yàn)+題目要求
對于本題而言就是：
dp[i][j]表示：走到[i,j]位置的時(shí)候，一共有多少種方式。
2.狀態(tài)轉(zhuǎn)移方程
機(jī)器人到達(dá)[i,j]位置有兩種，一種從上面過來，一種從左邊過來。
根據(jù)最近的一步劃分問題：
因此狀態(tài)方程為：
dp[i][j]=dp[i-1][j]+dp[i][j-1]
3.初始化
初始化之前先看一下會有什么位置會發(fā)生越界訪問：
因?yàn)闄C(jī)器人要么從上邊下來，要門從左邊下來，因此會發(fā)生越界的為第一排和第一列。
我們基本上會采取以下的初始化方式，在原二維數(shù)組的基礎(chǔ)上加一行一列。
加上之后要注意兩點(diǎn)：
下標(biāo)映射注意新表與原始的下標(biāo)關(guān)系即可，而虛擬節(jié)點(diǎn)里面的值要根據(jù)情況而定：
觀察一下，第二行從第三個(gè)開始需要它上面的和左面的兩個(gè)一起決定，而且要保證它上面的也就是虛擬節(jié)點(diǎn)不能被選上（也就是不影響結(jié)果）那么它應(yīng)該就是負(fù)無窮，但是本題的范圍：
所以我們賦值為0就不會被選上了。依次內(nèi)推：
因?yàn)榈诙诺牡诙€(gè)位置會決定其他位置的值，因此要賦值為1；這里有兩種，可以從上面虛擬節(jié)點(diǎn)也可以從左面的虛擬節(jié)點(diǎn)進(jìn)行賦值。
4.填表順序
整體從上往下，每排從左往右。
5.返回值
根據(jù)題目要求，需要返回右下角的值，因此返回：
dp[m][n]
代碼實(shí)現(xiàn)
動態(tài)規(guī)劃的代碼基本就是固定的四步：
1.創(chuàng)建dp表
2.初始化
3.填表
4.返回值
本題完整代碼實(shí)現(xiàn)：文章來源：http://www.zghlxwxcb.cn/news/detail-830798.html
class Solution
{
public:
int uniquePaths(int m, int n)
{
// 1.創(chuàng)建dp表
// 2.初始化
// 3.填表
// 4.返回值
vector<vector<int>> dp(m+1,vector<int>(n+1));
dp[0][1]=1;
//從上往下遍歷
for(int i=1;i<=m;i++)
{
//從左往右遍歷
for(int j=1;j<=n;j++)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m][n];
}
};
時(shí)間復(fù)雜度：O(MN)
空間復(fù)雜度：O(MN)文章來源地址http://www.zghlxwxcb.cn/news/detail-830798.html
到了這里，關(guān)于【動態(tài)規(guī)劃專欄】專題二：路徑問題--------1.不同路徑的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
