C++ DP動態規劃解Leetcode 937 Maximum Number of Points with Cost

C++ DP動態規劃解Leetcode 937  Maximum Number of Points with Cost

有些標示medium要比標示hard的問題還要難，Leetcode 1937. Maximum Number of Points with Cost，DP動態規劃可解，但怎麼樣的遞迴關係才能降低時間複雜度？

[Python解請進]

----------

Some problems labeled medium are more difficult than labeled hard. Leetcode 1937. Maximum Number of Points with Cost can be solved by DP dynamic programming, but what kind of recursive relationship can reduce the time complexity?

[codes on Leetcode]https://leetcode.com/problems/maximum-number-of-points-with-cost/solutions/5647848/recursive-iterative-dp-from-tle-to-138ms-beats-99-18/

[Dynamic programming playlist]https://www.youtube.com/watch?v=30yq3fmE6E8&list=PLYRlUBnWnd5K_XYUesV9oc6M9ONXII61T

[Leetcode Playlist]https://www.youtube.com/watch?v=B1GQlUN08lk&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        r, c=len(points), len(points[0])
        for i in range(1, r):
            left, right=[0]*c, [0]*c

            right[-1]=points[i-1][-1]
            for j in range(c-2, -1, -1):
                right[j]=max(right[j+1]-1, points[i-1][j])
            
            left[0]=points[i-1][0]
            points[i][0]=max(left[0], right[0])+points[i][0]
            for j in range(1, c):
                left[j]=max(left[j-1]-1, points[i-1][j])
                points[i][j]=max(left[j], right[j])+points[i][j]
                
        return max(points[-1])