Java | Bottom-Up DP + Recursion | O(n^2) Time Complexity
\n/*\n\nSuppose we have \'m\' elements in one array and \'n\' elements in another and we need to arrange \'n\' elemnts around \'m\' elements of first array with
```\n/*\n\nSuppose we have \'m\' elements in one array and \'n\' elements in another and we need to arrange \'n\' elemnts around \'m\' elements of first array without breaking the order of elements in any of the arrays.\n\narray first = _ l1 _ l2 _ l3 _ ..... _ li-2 _ li-1 _ li _ li+1 _ ..... _ lm-2 _ lm-1 _ lm _\n\narray second = r1 r2 r3 ..... rj-2 rj-1 rj rj+1 ..... rn-1 rn\n\nLet DP[i][j] = # of ways to arrange \'j\'th elements of second array around \'i\' elements of first array without breaking the order of elements in any of the arrays.\n\nFor placing the \'j\'th element (rj) of second array we have DP[i][j - 1] ways as \'j\'th element will follow order and will be placed only after \'j-1\'th element.\nAnd this \'j\' element could have occurred after \'i\'th element (li) of first array or after \'i-1\'th element (li-1) of first array or after \'i-2\'th element (li-2) of first array and so on.\n\nHence, we have\nDP[i][j] = DP[i][j - 1] + DP[i - 1][j - 1] + DP[i - 2][j - 1] + ..... + DP[0][j - 1] ; i E [1, m], j E [1, n], k E [0, i]\n\nIn General :\nDP[i][j] = sum(DP[i - k][j - 1])                                                     ; i E [1, m], j E [1, n], k E [0, i]\nDP[i][j] = 1                                                                         ; i == 0, j E [1, n]\nDP[i][j] = 1                                                                         ; i [1, m], j == 0\n\nresult = use DP to get solution by calling recursively for each subtree and multiply each combination.\nThen \'1\' is subtrated as we already have one combination given as input.\n\n-----------------------------------------------------------------------------------------------------------------\n\nMore formally :\nDP[i][j] = DP[i][j - 1] + DP[i - 1][j - 1] + DP[i - 2][j - 1] + ..... + DP[1][j - 1] + DP[0][j - 1] ; ..... (equation 1)\n\nPut \'i-1\' in place of \'i\' to get DP[i - 1][j]\nDP[i - 1][j] = DP[i - 1][j - 1] + DP[i - 2][j - 1] + DP[i - 3][j - 1] + ..... + DP[1][j - 1] + DP[0][j - 1] ; ..... (equation 2)\n\nSubtracting both above equations, we get\n(equation 1) - (equation 2)\n=> DP[i][j] - DP[i - 1][j] = DP[i][j - 1] ;\n=> DP[i][j] = DP[i][j - 1] + DP[i - 1][j] ;\n\n-----------------------------------------------------------------------------------------------------------------\n\nFinal equations :\nDP[i][j] = DP[i][j - 1] + DP[i - 1][j] ; i E [1, m], j E [1, n] ----- here m and n both are equal to length of the input array\nDP[i][j] = 1                           ; i == 0, j E [1, n]\nDP[i][j] = 1                           ; i [1, m], j == 0\n\nresult = use DP to get solution by calling recursively for each subtree and multiply each combination. Then \'1\' is subtrated as we already have one combination given as input.\n\n*/\n\nclass Solution {\n    public int numOfWays(int[] nums) {\n        int length = nums.length, MOD = 1000000007;\n        long[][] DP = new long[length + 1][length + 1];\n        for(int j = 0; j <= length; j++) {\n            DP[0][j] = 1;\n        }\n        for(int i = 0; i <= length; i++) {\n            DP[i][0] = 1;\n        }\n        for(int i = 1; i <= length; i++) {\n            for(int j = 1; j <= length; j++) {\n                DP[i][j] = ((DP[i][j - 1] + DP[i - 1][j]) % MOD);\n            }\n        }\n        return ((int) getNumberOfWays(nums, DP) - 1);\n    }\n\n    private long getNumberOfWays(int[] nums, long[][] DP) {\n        int length = nums.length, m = 0, n = 0, MOD = 1000000007;\n        if(length == 0) {\n            return 1;\n        }\n        for(int i = 2; i <= length; i++) {\n            if(nums[i - 1] < nums[0]) {\n                m++;\n            } else {\n                n++;\n            }\n        }\n        int[] leftNodes = new int[m];\n        int[] rightNodes = new int[n];\n        m = 0;\n        n = 0;\n        for(int i = 2; i <= length; i++) {\n            if(nums[i - 1] < nums[0]) {\n                leftNodes[m++] = nums[i - 1];\n            } else {\n                rightNodes[n++] = nums[i - 1];\n            }\n        }\n        return (((DP[m][n] * getNumberOfWays(leftNodes, DP) % MOD) * getNumberOfWays(rightNodes, DP)) % MOD);\n    }\n}\n```
[]