C++ Space Optimized Iterative + Recursive DP Solution
Complexity\n- Time complexity: $O(n)$\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: $O(1)$ for Space Optimized Iterative and $O(n)$ for Rec
# Complexity\n- Time complexity: $O(n)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(1)$ for Space Optimized Iterative and $O(n)$ for Recursive\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\n// Iterative\nclass Solution {\npublic:\n    int maxNonDecreasingLength(vector<int>& a, vector<int>& b) {\n        const int n = (int)a.size();\n        if (n == 1) return 1;\n        vector<vector<int>> dp(2, vector<int>(2, 0));\n        int ans = 1;\n        for (int idx = n; idx >= 1; idx--) {\n            for (int t = 0; t < 2; t++) {\n                int i = idx & 1;\n                dp[i][t] = 0;\n                if (idx == n) continue;\n                int p = (t? a[idx - 1]: b[idx - 1]);\n                if (p <= a[idx]) dp[i][t] = max(dp[i][t], 1 + dp[1 - i][1]);\n                if (p <= b[idx]) dp[i][t] = max(dp[i][t], 1 + dp[1 - i][0]);\n                ans = max({ans, dp[i][1] + 1, dp[i][0] + 1});\n            }\n        }\n        return ans;\n    }\n};\n```\n```cpp []\n// Recursive\nclass Solution {\npublic:\n    int maxNonDecreasingLength(vector<int>& a, vector<int>& b) {\n        const int n = (int)a.size();\n        if (n == 1) return 1;\n        vector<vector<int>> dp(n + 1, vector<int>(2, -1));\n        function<int(int, int)> f = [&](int i, int t) -> int {\n            if (i == n) return 0;\n            int& ans = dp[i][t];\n            if (ans != -1) return ans;\n            ans = 0;\n            int p = (t? a[i - 1]: b[i - 1]);\n            if (p <= a[i]) ans = max(ans, 1 + f(i + 1, 1));\n            if (p <= b[i]) ans = max(ans, 1 + f(i + 1, 0));\n            return ans;\n        };\n        int ans = 1;\n        for (int i = 1; i < n; i++) {\n            ans = max({ans, f(i, 1) + 1, f(i, 0) + 1});\n        }\n        return ans;\n    }\n};\n```\n\n# Blog \n- How to convert almost all **Recursive DP** to **Iterative DP** with Space Optimization: https://medium.com/@dhavalkumar741/how-to-convert-almost-all-recursive-dp-to-iterative-dp-babaaff0363d\n
['Dynamic Programming', 'C++']