Java | Iterative DP | 2 Codes
Update.\nThanks to the top-voted post @DBabichev. I implemented his/her/their idea in Java here. \nA bit slower than my first version (464ms) but a lot more con
#### Update.\nThanks to the top-voted post @DBabichev. I implemented his/her/their idea in Java here. \nA bit slower than my first version (464ms) but a lot more concise.\n#### Java\n```Java\nclass Solution {\n    public int minimumIncompatibility(int[] nums, int k) {\n        Arrays.sort(nums);\n        k=nums.length/k;\n        int n = nums.length,INF=100;\n        int[][] dp = new int[1<<n][n];\n        for (int[] d : dp){\n            Arrays.fill(d, INF);\n        }\n        for (int i=0;i<n;i++){\n            dp[1<<i][i]=0;\n        }\n        for (int i = 1; i < 1<<n; i++){\n            int c = Integer.bitCount(i);\n            for (int j=0;j<n&&c%k==0;j++){\n                for (int w=0;w<n&&(i&1<<j)>0;w++){\n                    if ((i&1<<w)==0){\n                        dp[i|1<<w][w]=Math.min(dp[i|1<<w][w], dp[i][j]);\n                    }\n                }\n            }\n            for (int j=0;j<n&&c%k!=0;j++){\n                for (int w=j+1;w<n&&(i&1<<j)>0;w++){\n                    if ((i&1<<w)==0&&nums[w]!=nums[j]){\n                        dp[i|1<<w][w]=Math.min(dp[i|1<<w][w], dp[i][j]+nums[w]-nums[j]);\n                    }\n                }\n            }\n        }\n        int ans = Arrays.stream(dp[(1<<n)-1]).min().getAsInt();\n        return ans==INF?-1:ans;\n    }\n}\n```\n#### OLD\nNot the way we are supposed to do bottom-up DP, but I could only come up with 2 bottom-up DP approaches.\n1. Get the base case first and use submask trick. This will result in a lot of unnecessary computation as we will be skipping lots of masks whose bit set isn\'t `n/k`. will run in `O(3^n)`.\n\n2. Go for `O(2^n)` & don\'t use submask trick but use bitset to prune masks. This should ideally be faster? I am not quite sure. Depending on test cases.\n\nHere I am presenting the second way.\n\nIt passed (AC) with average speed (about 300ms).\n\n#### Java\n```Java\nclass Solution {\n    public int minimumIncompatibility(int[] nums, int k) {\n        int n = nums.length/k,cnt=0,INF=100;\n        BitSet[] bits = new BitSet[nums.length];\n        Arrays.setAll(bits, o -> new BitSet());\n        int[] dp = new int[1<<nums.length];\n        int[] map = new int[1<<nums.length];\n        Arrays.fill(dp, INF);\n        int[] seen = new int[nums.length+1];\n        for (int i = 0; i < nums.length; i++){\n            seen[nums[i]]=i;\n        }\n        for (int v = (1<<n)-1; v<1<<nums.length; v=next(v)){ // base case\n            int max = 0, min = INF;\n            boolean ok = true;\n            for (int j = 0; j < nums.length&&ok; j++){\n                if ((v&1<<j)>0){\n                    ok &= !(seen[nums[j]]!=j&&(v&1<<seen[nums[j]])>0);\n                    seen[nums[j]]=j;\n                    min=Math.min(min, nums[j]);\n                    max=Math.max(max, nums[j]);\n                }\n            }\n            for (int j = 0; j < nums.length && ok; j++){\n                if ((v&1<<j)==0){\n                    bits[j].set(cnt); // set the mask\n                }\n            }\n            if (ok){\n                dp[v]=max-min;\n                map[cnt++]=v;\n            }\n        }\n        for (int i = 1; i < k; i++){ // DP\n            for (int v = (1<<i*n)-1; v<1<<nums.length; v=next(v)){\n                BitSet cur = new BitSet();\n                cur.set(0, cnt);\n                for (int j = 0; j < nums.length; j++){\n                    if ((v&1<<j)>0){ // prune unfit (contradictory) candidates\n                        cur.and(bits[j]);\n                    }\n                }\n                for (int j = cur.nextSetBit(0); j>=0; j=cur.nextSetBit(j+1)){\n                    dp[map[j]|v]=Math.min(dp[map[j]|v],dp[map[j]]+dp[v]);\n                }\n            }\n        }\n        return dp[(1<<nums.length)-1]==INF?-1:dp[(1<<nums.length)-1];\n    }\n\n    private int next(int v){ // gen the next mask\n        int t = (v | (v - 1)) + 1;\n        v = t | ((((t & -t) / (v & -v)) >> 1) - 1);\n        return v;\n    }\n}\n```
['Dynamic Programming', 'Java']