C++ dp動態規劃解leetcode 2369 Check if There is a Valid Partition For The Array

C++ dp動態規劃解leetcode 2369 Check if There is a Valid Partition For The Array

這是一個DP問題。 使用一維陣列 DP 來存儲狀態。 使用自上而下的設計。 實現了具有記憶功能的遞迴程式。 第二種方法使用優化空間 O(1) 的自下而上設計。 由於計算時只考慮 dp[i-2]、dp[i-1]、dp[i] 和 dp[i+1] 4 個狀態。 索引模 4 足以滿足我們的實現。

-

[codes on Leetcode]https://leetcode.com/problems/check-if-there-is-a-valid-partition-for-the-array/solutions/3901300/c-recursive-dp-vs-iterative-dp/

[LeetCode程式]https://www.youtube.com/watch?v=7g-E3d_Oja4&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk&index=1

--------

This i s a DP problem. Use 1D array DP for storing the states. Use top-down design. A recursive program with memozation is implemented.  The second approach uses buttom-up design with optimized space O(1). Since there are only 4 states dp[i-2], dp[i-1], dp[i] & dp[i+1] to be considered in computation. Index number modulo 4 suffices for our implementation.