關(guān)于動態(tài)規(guī)劃法的解釋, 大多都是基于背包問題的, 但背包問題背負了很多算法的解釋工作,經(jīng)常讓初學(xué)者混淆,剛剛刷leetcode的時候,發(fā)現(xiàn)了一個很不錯的關(guān)于動態(tài)規(guī)劃算法的例題,特來分享一下!
Leetcode120
這是一個典型的動態(tài)規(guī)劃問題:
- 在走第N步的之前, 第1步到第N-1步已經(jīng)達到了最優(yōu).
- 走出第N步之后, 第N-1步的最優(yōu)就要動態(tài)變化為"相對最優(yōu)",而第一步到第N步依然是最優(yōu).
動態(tài)規(guī)劃法的優(yōu)勢在于, 前面N-1步保持了"很多"狀態(tài), 當(dāng)走出第N-1步的時候后, 可以基于保存的狀態(tài)直接得出"很多新的"狀態(tài), 然后從新狀態(tài)中得到最優(yōu)解.
為了簡化問題, 對于上面的題目,我們可以從底向上走:
動態(tài)規(guī)劃法
class Solution:
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
for m in range(len(triangle)-1)[::-1]:
# m 為 主數(shù)組索引
if (m == len(triangle)-1):
pass
# n 為當(dāng)前元素索引
for n in range(len(triangle[m])):
triangle[m][n] = min(triangle[m][n]+triangle[m+1][n], triangle[m][n]+triangle[m+1][n+1])
print("第",m,"行", "第",n,"個元素當(dāng)前值為", triangle[m][n])
return triangle[0][0]
def main():
result = Solution().minimumTotal([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]])
print("最短路徑為==>",result)
if __name__ == '__main__':
main()
動態(tài)規(guī)劃法結(jié)果
動態(tài)規(guī)劃與貪心法的區(qū)別:
- 貪心只考慮當(dāng)前最優(yōu), 只保留當(dāng)前最優(yōu)的狀態(tài);
- 動態(tài)規(guī)劃法, 不僅保留了當(dāng)前最優(yōu),而且保留了(很多)相對最優(yōu)的狀態(tài)
