Py3 C++ DP動態規劃速解Leetcode 120 Triangle

Py3 C++ DP速解Leetcode 120  Triangle

這題就是用動態規劃解，表列法比較容易

[Py3解請進]

------

This problem is solved by dynamic programming, and the tabular method is easier

[codes on Leetcode]https://leetcode.com/problems/triangle/solutions/7221419/recursive-dp-vs-iterative-dp-with-o-1-space-beats-100/

[DP動態規劃playlist]https://www.youtube.com/watch?v=30yq3fmE6E8&list=PLYRlUBnWnd5K_XYUesV9oc6M9ONXII61T

class Solution:
    def minimumTotal(self, t: List[List[int]]) -> int:
        n=len(t)
        for i in range(1, n):
            t[i][0]+=t[i-1][0]
            t[i][i]+=t[i-1][i-1]
            for j in range(1, i):
                t[i][j]+=min(t[i-1][j], t[i-1][j-1])
        return min(t[-1])