# 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];
}```
Share

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;
}```