力扣題目：#62.不同路徑
刷題時(shí)長：參考題解后10min
解題方法：動(dòng)規(guī)
復(fù)雜度分析
- 時(shí)間O(m*n)
- 空間O(m*n)
問題總結(jié)文章來源：http://www.zghlxwxcb.cn/news/detail-532649.html
- 初始化二維數(shù)組的python語法：i 對應(yīng) m，j 對應(yīng)n
- 二維遍歷順序，從上到下從左到右通過兩層for循環(huán)實(shí)現(xiàn)，其中startindex應(yīng)為1
本題收獲文章來源地址http://www.zghlxwxcb.cn/news/detail-532649.html
- 動(dòng)規(guī)思路
- 確定dp數(shù)組及下標(biāo)的含義：dp[i][j] 表示從（0，0）出發(fā)，到(i, j) 有dp[i][j]條不同的路徑
- 確定遞推公式：dp[i][j] = dp[i - 1][j] +?dp[i][j - 1]
- dp數(shù)組的初始化：題目說只能往下或往右走，所以dp[i][0]都是1，因?yàn)閺?0, 0)的位置到(i, 0)的路徑只有一條。dp[0][j]同理都初始化為1
- 確定遍歷順序：dp[i][j]都是從其上方和左方推導(dǎo)而來，那么從左到右一層一層遍歷就可以保證推導(dǎo)dp[i][j]的時(shí)候，dp[i - 1][j] 和 dp[i][j - 1]一定是有數(shù)值的
力扣題目：#63. 不同路徑 II
刷題時(shí)長：30min
解題方法：動(dòng)規(guī)
復(fù)雜度分析
- 時(shí)間O(m*n)
- 空間O(m*n)
問題總結(jié)
- 思路都對了，語法錯(cuò)誤沒debug出來，少了個(gè)break
- 需提前判斷邊界情況，若起始位置和終止位置若有障礙物，直接返回0
本題收獲
- dp數(shù)組初始化：一旦遇到obstacleGrid[i][0] == 1的情況就停止dp[i][0]的賦值1的操作，dp[0][j]同理。因?yàn)閺?0, 0)的位置到(i, 0)的路徑只有一條，所以dp[i][0]一定為1，dp[0][j]也同理。但如果(i, 0) 這條邊有了障礙之后，障礙之后（包括障礙）都是走不到的位置了，所以障礙之后的dp[i][0]應(yīng)該還是初始值0。
到了這里，關(guān)于力扣算法刷題Day39｜動(dòng)態(tài)規(guī)劃：不同路徑 I&II的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
