python C++DP動態規劃解Leetcode 678 Valid Parenthesis String

python C++DP動態規劃解Leetcode 678  Valid Parenthesis String

使用2D DP來求解。 由於 n≤100，因此帶有 memo 的遞迴可以完成這項工作。 知道了遞迴那麼DP就一定可行！

第二種方法是迭代 DP 程式碼； 使用 &1 技巧減少空間至O(n)。Python code請進 。

------

Use 2D DP to solve. Since n≤100, recursion with memo does the job. If you know how to pass it back, DP will work!

The second approach is to reduce the space of the iterative DP code to O(n); use the &1 trick.

[codes on Leetcode]https://leetcode.com/problems/valid-parenthesis-string/solutions/4985180/recursive-dp-iterative-dp-vs-greedy-0ms-beats-100/

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

[Prefix Sum playlist]https://www.youtube.com/watch?v=FGDkETbwWHc&list=PLYRlUBnWnd5LkYN-5ptHDrtPXOuHm9uSq&index=1

class Solution:
	def checkValidString(self, s: str) -> bool:
		n=len(s)
		@cache
		def f(i, balance):
			if i==n: return balance==0
			if balance<0: return False
			ans=False
			if s[i]=='(': ans=f(i+1, balance+1)
			elif s[i]==')': ans=f(i+1, balance-1)
			else: ans=f(i+1, balance+1) or f(i+1, balance) or f(i+1, balance-1)
			return ans
		return f(0, 0)