From Recursion to DP (4 Solutions) [Java]
Approach\nThere are two states possible,\n1. Don\'t swap elements at the current index\n2. Swap elements at the current index\n\nWe just have to find out which 
**Approach**\nThere are two states possible,\n1. Don\'t swap elements at the current index\n2. Swap elements at the current index\n\nWe just have to find out which one gives the minimum number of swaps for the rest of the array. That is, we will compute answer for both the states. The answer for the current state is dependent on the relation between the element at the current index and the previous index.\n\nIf they are already in increasing order, then the state for the current index is applied to the previous index (that is, no swap remains no swap, swap remains swap). Else, the state for the current index is reversed for the previous index. But, what if swap and no swap both achieve the increasing order? In this case, we take the minimum of both states from the previous index.\n\n**Implementations**\nN = size of nums1/nums2 array\n\n**1. Recursion**\nTime complexiy: O(2^N)\nSpace complexity: O(N)\n\n```java\nclass Solution {\n    public int minSwap(int[] nums1, int[] nums2) {\n        return Math.min(recurse(nums1, nums2, nums1.length - 1, 0),\n                        recurse(nums1, nums2, nums1.length - 1, 1));\n    }\n    \n    private int recurse(int[] nums1, int[] nums2, int i, int swap) {\n        // base case\n        if (i == 0)\n            return swap;\n        \n        // default is set as max\n        int res = Integer.MAX_VALUE;\n        \n        // if array is increasing without swapping\n        if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1])\n                res = recurse(nums1, nums2, i - 1, swap);\n        \n        // if array is increasing with swapping\n        if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1])\n                res = Math.min(res, \n                               recurse(nums1, nums2, i - 1, 1 - swap));\n        \n        return swap == 0 ? res : res + 1;\n    }\n}\n```\n\n**2. Memoization**\nTime complexiy: O(N)\nSpace complexity: O(N)\n\n```java\nclass Solution {\n    public int minSwap(int[] nums1, int[] nums2) {\n        int n = nums1.length;\n        \n        // initialize dp table\n        int[][] memo = new int[2][n];\n        Arrays.fill(memo[0], -1);\n        Arrays.fill(memo[1], -1);\n        memo[0][0] = 0;\n        memo[1][0] = 1;\n        \n        return Math.min(recurse(nums1, nums2, n - 1, 0, memo),\n                        recurse(nums1, nums2, n - 1, 1, memo));\n    }\n    \n    private int recurse(int[] nums1, int[] nums2, int i, int swap, int[][] memo) {\n        //check dp table\n        if (memo[swap][i] != -1)\n            return memo[swap][i];\n        \n        // initial value is set as max\n        int res = Integer.MAX_VALUE;\n        \n        // if array is increasing without swapping\n        if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1])\n                res = recurse(nums1, nums2, i - 1, swap, memo);\n        \n        // if array is increasing with swapping\n        if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1])\n                res = Math.min(res, \n                               recurse(nums1, nums2, i - 1, 1 - swap, memo));\n        \n        memo[swap][i] = swap == 0 ? res : res + 1;\n        return memo[swap][i];\n    }\n}\n```\n\n**3. Tabulation**\nTime complexiy: O(N)\nSpace complexity: O(N)\n\n```java\nclass Solution {\n    public int minSwap(int[] nums1, int[] nums2) {\n        int n = nums1.length;\n        \n        // initialize dp table\n        int[][] table = new int[2][n];\n        table[0][0] = 0;\n        table[1][0] = 1;\n        \n        for (int i = 1; i < n; i++) {\n            // initial value\n            table[0][i] = Integer.MAX_VALUE;\n            table[1][i] = Integer.MAX_VALUE;\n            \n            // if array is increasing without swapping\n            if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {\n                table[0][i] = table[0][i - 1];\n                table[1][i] = 1 + table[1][i - 1];\n            }\n            \n             // if array is increasing with swapping\n            if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {\n                table[0][i] = Math.min(table[0][i], table[1][i - 1]);\n                table[1][i] = Math.min(table[1][i], 1 + table[0][i - 1]);\n            }\n        }\n        \n        return Math.min(table[0][n - 1], table[1][n - 1]);\n    }\n}\n```\n\n**4. Tabulation with Constant Space**\nTime complexiy: O(N)\nSpace complexity: O(1)\n\n```java\nclass Solution {\n    public int minSwap(int[] nums1, int[] nums2) {\n        int n = nums1.length;\n        \n        // initialize current res\n        int curNoSwap = 0, curSwap = 1;\n        \n        for (int i = 1; i < n; i++) {\n            // update previous values\n            int prevNoSwap = curNoSwap, prevSwap = curSwap;\n            \n            // reset cur values\n            curNoSwap = Integer.MAX_VALUE;\n            curSwap = Integer.MAX_VALUE;\n            \n           // if array is increasing without swapping\n            if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {\n                curNoSwap = prevNoSwap;\n                curSwap = 1 + prevSwap;\n            }\n            \n            // if array is increasing with swapping\n            if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {\n                curNoSwap = Math.min(curNoSwap, prevSwap);\n                curSwap = Math.min(curSwap, 1 + prevNoSwap);\n            }\n        }\n        \n        return Math.min(curNoSwap, curSwap);\n    }\n}\n```
['Dynamic Programming', 'Recursion', 'Java']