#46 Coding 面試 - LeetCode #62 Unique Paths

原文網址 https://leetcode.com/problems/unique-paths/

這一題主要是考 dynamic programming 的思考,但老實說,這題過於直覺,所以寫完答案時還沒馬上觀察到這是 dynamic programming 的解法


參考的解法如下:



從 First row 上的可行走法都是1, 因為只有可能從左邊走過來的方式.從 second row 開始,就有可能是從上面或從左邊來的走法,因此才是相加的,也就是上述解法中 r[i,j] = r[i-1,j] + r[i,j-1];

我相信如果你的主考官想要考你 dynamic programming 的話,應該不會用這一題來考你.若是要考簡單的,應該會是用 Fibonacci number 來考你,因為最直覺的 Fibonacci number 的寫法並不是用 dynamic programming 的寫法,而是用 recursive 的寫法.以時間複雜度來看,dynamic programming 的寫法是比較快的,而以空間複雜度來看,recursive 寫法是比較優的.

Share:

0 意見:

張貼留言