Bottom-up DP with Optimization (Java / Python)
state\t\nwhether we swap the element at index i to make A[0..i]  and B[0..i] both increasing can uniquely identify a\xA0state, i.e. a node in the state graph.\n
**state**\t\nwhether we swap the element at index i to make A[0..i]  and B[0..i] both increasing can uniquely identify a\xA0state, i.e. a node in the state graph.\n**state function**\t\n`state(i, 0)`\xA0is the minimum swaps to make A[0..i] and B[0..i] both increasing if we donot swap A[i] with B[i]\n`state(i, 1)`\xA0is the minimum swaps to make A[0..i] and B[0..i] both increasing if we do swap A[i] with B[i]\n**goal state**\t\n`min{state(n - 1, 0), state(n - 1, 1)}` where n = A.length\n**state transition**\t\nWe define `areBothSelfIncreasing: A[i - 1] < A[i] && B[i - 1] < B[i], areInterchangeIncreasing: A[i - 1] < B[i] && B[i - 1] < A[i]`.\nSince *\'the given input always makes it possible\'*, at least one of the two conditions above should be satisfied.\n```\nif i == 0, \n\t        state(0, 0) = 0; \n\t        state(0, 1) = 1;\n\t\t\t\nGenerally speaking,\n\tif areBothSelfIncreasing && areInterchangeIncreasing\n\t        // Doesn\'t matter whether the previous is swapped or not.\n\t        state(i, 0) = Math.min(state(i - 1, 0), state(i - 1, 1));\n\t        state(i, 1) = Math.min(state(i - 1, 0), state(i - 1, 1)) + 1;\n\telse if areBothSelfIncreasing\n\t        // Following the previous action.\n\t        state(i, 0) =  state(i - 1, 0);\n\t        state(i, 1) =  state(i - 1, 1) + 1;\n\telse if areInterchangeIncreasing\n\t        // Opposite to the previous action.\n\t        state(i, 0) = state(i - 1, 1);\n\t        state(i, 1) = state(i - 1, 0) + 1;\n```\n**Java 0.0**\n```\n    public int minSwap(int[] A, int[] B) {\n        int n = A.length;\n        \n        /* \n\t\t state[i][0] is min swaps too make A[0..i] and B[0..i] increasing if we do not swap A[i] and B[i]; \n\t\t state[i][1] is min swaps too make A[0..i] and B[0..i] increasing if we swap A[i] and B[i].\n         */\n        int[][] state = new int[n][2];\n        state[0][1] = 1;\n        \n        for (int i = 1; i < n; i++) {\n            boolean areBothSelfIncreasing = A[i - 1] < A[i] && B[i - 1] < B[i];\n            boolean areInterchangeIncreasing = A[i - 1] < B[i] && B[i - 1] < A[i];\n            \n            if (areBothSelfIncreasing && areInterchangeIncreasing) {\n                state[i][0] = Math.min(state[i - 1][0], state[i - 1][1]);\n                state[i][1] = Math.min(state[i - 1][0], state[i - 1][1]) + 1;\n            } else if (areBothSelfIncreasing) {\n                state[i][0] = state[i - 1][0];\n                state[i][1] = state[i - 1][1] + 1;\n            } else { // if (areInterchangeIncreasing)\n                state[i][0] = state[i - 1][1];\n                state[i][1] = state[i - 1][0] + 1;\n            }\n        }\n        \n        return Math.min(state[n - 1][0], state[n - 1][1]);\n    }\n```\n**Optimization**\nSince current state depends on its previous state only, we may use variables to save states rather than the state array.\n**Java 0.1**\n```\n    public int minSwap(int[] A, int[] B) {\n        int n = A.length, prevNotSwap = 0, prevSwap = 1;\n        \n        for (int i = 1; i < n; i++) {\n            boolean areBothSelfIncreasing = A[i - 1] < A[i] && B[i - 1] < B[i];\n            boolean areInterchangeIncreasing = A[i - 1] < B[i] && B[i - 1] < A[i];\n            \n            if (areBothSelfIncreasing && areInterchangeIncreasing) {\n                int newPrevNotSwap = Math.min(prevNotSwap, prevSwap);\n                prevSwap = Math.min(prevNotSwap, prevSwap) + 1;\n                prevNotSwap = newPrevNotSwap;\n            } else if (areBothSelfIncreasing) {\n                prevSwap++;\n            } else { // if (areInterchangeIncreasing)\n                int newPrevNotSwap = prevSwap;\n                prevSwap = prevNotSwap + 1;\n                prevNotSwap = newPrevNotSwap;\n            }\n        }\n        \n        return Math.min(prevSwap, prevNotSwap);\n    }\n```\n**Python**\n```\n    def minSwap(self, A, B):\n        n = len(A)\n        prevNotSwap = 0\n        prevSwap = 1\n        for i in range(1, n):\n            areBothSelfIncreasing = A[i - 1] < A[i] and B[i - 1] < B[i] \n            areInterchangeIncreasing = A[i - 1] < B[i] and B[i - 1] < A[i]\n            if areBothSelfIncreasing and areInterchangeIncreasing:\n                newPrevNotSwap = min(prevNotSwap, prevSwap)\n                prevSwap = min(prevNotSwap, prevSwap) + 1\n                prevNotSwap = newPrevNotSwap\n            elif areBothSelfIncreasing:\n                prevSwap += 1 \n            else: # if areInterchangeIncreasing:\n                newPrevNotSwap = prevSwap\n                prevSwap = prevNotSwap + 1\n                prevNotSwap = newPrevNotSwap\n        return min(prevNotSwap, prevSwap)\n```\n**(\u4EBA \u2022\u0348\u1D17\u2022\u0348)** Thanks for voting!
[]