前端算法題之動態(tài)規(guī)劃入門題：機器人走路
題目：給定一個 n * m 的矩陣 a，從左上角開始每次只能向右或者向下走，最后到達右下角的位置，路徑上所有的數(shù)字累加起來就是路徑和，輸出所有的路徑中最小的路徑和。
實例：
輸入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]
輸出12
分析題目：
只有兩個方向
一次只能走一個方向
最上邊只有來至左邊一個方向
最左邊只有來至上邊一個方向
當前位置的總數(shù)永遠等于上一個位置的總數(shù)加上當前位置的數(shù)
兩種位移方式但只取數(shù)最小的那種方式。
實現(xiàn)：
這里每一個位置的數(shù)都是上一個位置的數(shù)加上方向上最小的數(shù)，但是這其中有N個數(shù)是重復計算的，因此需要存儲起來方便后面直接調(diào)用。因為存在兩個方向，因此存儲的結構應該是一個二維數(shù)組。
不足之處麻煩指出，謝謝！
標簽：
