Easy to Understand DP solution in java
Intuition\nIntuition for this problem was quite obvious, at every index, we have two operations either we pick the element from first array or we pick the eleme
# Intuition\nIntuition for this problem was quite obvious, at every index, we have two operations either we pick the element from first array or we pick the element from second array. So we will be using dp to solve this question.\n\n# Approach\nI have taken two states one is index which will be used to traverse the array and second is pick, it denotes whether the last element was picked from first array or second array if pick==1 then it means it the last element was picked from first array, if pick==2 then it means the last element was picked from the second array but if pick==0, then it means no element has been picked yet.\n\n# Complexity\n- Time complexity:\n\nThe time complexity of dp solution is the product of the states, here in this case value of index will range from (1 to n) and value of pick will range from (0 to 2), so the T.C. would be O(N*2) which will be equal to O(N).\n\n# Code\n```\nclass Solution {\n    public int solve(int i,int prev,int[] nums1,int[] nums2,int[][] dp)\n    {\n        if(i>=nums1.length) return 0;             \n        if(dp[i][prev]!=-1) return dp[i][prev];\n        int ans=0;\n        if(prev==0)\n        {\n            ans = solve( i +1, 0,nums1,nums2,dp);\n            int take1=1+solve(i+1,1,nums1,nums2,dp);    \n            int take2=1+solve(i+1,2,nums1,nums2,dp);    \n            ans=Math.max(ans,Math.max(take1,take2));            \n           \n        }\n        else if(prev==1)                         \n        {\n            if(nums1[i]>=nums1[i-1]) ans = Math.max(ans,1+solve(i+1,1,nums1,nums2,dp)); \n            if(nums2[i]>=nums1[i-1]) ans = Math.max(ans,1+solve(i+1,2,nums1,nums2,dp));    \n        }\n        else if(prev==2)          \n        {\n            if(nums1[i] >=nums2[i-1]) ans = Math.max(ans,1+solve(i+1,1,nums1,nums2,dp));               \n            if(nums2[i]>=nums2[i-1]) ans = Math.max(ans,1+solve(i+1,2,nums1,nums2,dp));               \n        }          \n\n        return dp[i][prev]= ans;\n    }\n    public int maxNonDecreasingLength(int[] nums1, int[] nums2) {\n        int[][] dp = new int[nums1.length][3];\n        for(int[] row: dp)\n         Arrays.fill(row,-1);\n        return solve(0,0,nums1,nums2,dp);\n    }\n}\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'Java']