K Sum

Lintcode Online Judge

Given n distinct positive integers, integer k (k <= n) and a number target.

Find k numbers where sum is target. Calculate how many solutions there are?

 Example

Given [1,2,3,4], k = 2, target = 5.

There are 2 solutions: [1,4] and [2,3].

Return 2.

Solution: DP

state:  f[i][j][t]前i个数取j个数出来能否和为t

function: f[i][j][t] = f[i – 1][j – 1][t – a[i]] //取Ai的情况

+ f[i – 1][j][t]//不取Ai的情况

init: f[x][0][0] = 1

O(n*k*t) time O(n*k*t) space

public int kSum(int A[], int k, int target) {
    if (A == null) {
        return 0;
    }
    //kSum[i][j][t]:find j integers from first i integers in the array
    //how many solutions there are to sum up to t
    int[][][] kSum = new int[A.length + 1][k + 1][target + 1];
    for (int i = 0; i <= A.length; i++) {
        kSum[i][0][0] = 1; //select nothing which is also a solution
    }
    for (int i = 1; i <= A.length; i++) {
        for (int j = 1; j <= k; j++) {
            for (int t = 1; t <= target; t++) {
                kSum[i][j][t] = kSum[i - 1][j][t];
                if (t >= A[i - 1]) {
                    kSum[i][j][t] += kSum[i - 1][j - 1][t - A[i - 1]];
                }
            }
        }
    }
    return kSum[A.length][k][target];
}
FacebookTwitterGoogle+Share

Minimum Adjustment Cost

Online Judge

Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target.

If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|

Example

Given [1,4,2,3] and target = 1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it’s minimal.

Return 2.

Note

You can assume each number in the array is a positive integer and not greater than 100.

Solution: DP

state: f[i][v] 前i个数,第i个数调整为v,满足相邻两数<=target,所需要的最小代价

function: f[i][v] = min(f[i-1][v’] + |A[i]-v|, |v-v’| <= target)

Time Complexity: O(m*n*t) m: array size n:最大可能的数 t:required range

Space Complexity: O(m*n)

 

public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
    if (A == null || A.size() <= 1) {
        return 0;
    }
    int maxInt = 100;//assume each number in the array is a positive integer and not greater than 100
    int[][] minCost = new int[A.size() + 1][maxInt + 1];
    for (int i = 0; i <= maxInt; i++) {
        minCost[0][i] = 0;
    }
    for (int i = 1; i <= A.size(); i++) {
        for (int j = 0; j <= maxInt; j++) {
            int costAiToJ = Math.abs(A.get(i - 1) - j);
            int min = Integer.MAX_VALUE;
            //|k-j|<=target
            //max(0, j-target) <= k <= min(target+j, maxInt)
            for (int k = Math.max(0, j - target); k <= Math.min(target + j, maxInt); k++) {
                if (minCost[i - 1][k] + costAiToJ < min) {
                    min = minCost[i - 1][k] + costAiToJ;
                }
            }
            minCost[i][j] = min;
        }
    }
    int finalMinCost = minCost[A.size()][0];
    for (int i = 0; i <= maxInt; i++) {
        if (minCost[A.size()][i] < finalMinCost) {
            finalMinCost = minCost[A.size()][i];
        }
    }
    return finalMinCost;
}