# 1066. Campus Bikes II

``````
// Plain backtracking
class Solution {
int min = Integer.MAX_VALUE;
public int assignBikes(int[][] workers, int[][] bikes) {
int m = bikes.length;
boolean[] used = new boolean[m];
dfs(0, workers, bikes, 0, used);
return min;
}

private void dfs(int workerIndex, int[][] workers,
int[][] bikes, int sum, boolean[] used) {
if (workerIndex == workers.length) {
min = Math.min(min, sum);
return;
}

if (sum > min) return;

for (int i = 0; i < bikes.length; i++) {
if (!used[i]) {
used[i] = true;
dfs(workerIndex + 1, workers, bikes, sum +
distance(workers[workerIndex], bikes[i]), used);
used[i] = false;
}
}
}

private int distance(int[] worker, int[] bike) {
return Math.abs(worker - bike) + Math.abs(worker - bike);
}
}

// State reducing dynamic programming
class Solution {
public int assignBikes(int[][] workers, int[][] bikes) {
int n = bikes.length;
int[] dp = new int[1 << n];
return dfs(workers, bikes, 0, 0, dp);
}

private int dfs(int[][] workers, int[][] bikes,
int workerIndex, int state, int[] dp) {
if (workerIndex == workers.length) return 0;
if (dp[state] != 0) return dp[state];
int min = Integer.MAX_VALUE;

for (int i = 0; i < bikes.length; i++) {
if ((state & (1 << i)) == 0) {
min = Math.min(min, Math.abs(workers[workerIndex] - bikes[i]) +
Math.abs(workers[workerIndex] - bikes[i]) +
dfs(workers, bikes, workerIndex + 1, state | (1 << i), dp));
}
}

dp[state] = min;
return min;
}
}

``````