DP的其他两个题目

剩下两个非典型的DP， 实在是懒得写了，把链接和source code放这里参考吧，我也是看了答案做的，觉得就算让我再碰到我也是不会。。。LOL

Minimum Adjustment Cost 

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]|

Have you met this question in a real interview? 

Yes

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

class Solution { public: /** * @param A: An integer array. * @param target: An integer. */ int MinAdjustmentCost(vector<int> A, int target) { // write your code here int n=A.size(); if (n==0) return INT_MAX; // state 第i个元素调整到j的最小代价 int max_val=100; int f[n][max_val+1]; // initialize 第0 个元素调整为j的代价 for (int j=0; j<=max_val; j++){ f[0][j]=abs(A[0]-j); } //状态转移方程 for (int i=1; i<n; i++){ for (int j=0; j<=max_val; j++){ f[i][j]=INT_MAX; // loop j+-target for 前i-1个元素 for (int k=j-target; k<=j+target; k++){ if (k<0 || k>max_val) continue; // 第i个不放，那么保证i-1和i的差为target，则j // 在[j-target, j+target]之间，且从f[i-1][k]到 // f[i][j]代价为f[i-1][k]+abs(j-A[i]) f[i][j]=min(f[i][j], f[i-1][k]+abs(j-A[i])); } } } int res=INT_MAX; // final state for (int j=0; j<=max_val; j++){ res=min(res,f[n-1][j]); } return res; } };

K SUM 这个还是有的一做的，那些2,3,4sum什么的这里用o(n^3)秒杀了，当然仅仅限于3sum以后了。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

class Solution { public: /** * @param A: an integer array. * @param k: a positive integer (k <= length(A)) * @param target: a integer * @return an integer */ int kSum(vector<int> A, int k, int target) { // wirte your code here int n=A.size(); int f[n+1][k+1][target+1]; // first i numbers geting j numbers for form k for (int i=0; i<=n; i++){ for (int j=0; j<=k; j++){ for (int t=0; t<=target; t++){ f[i][j][t]=0; } } } // initial state for (int i=0; i<=n; i++){ f[i][0][0]=1; } // function for (int i=1; i<=n; i++){ for (int j=1; j<=k && j<=i; j++){ for (int t=0; t<=target; t++){ f[i][j][t]=f[i-1][j][t]; if (t-A[i-1]>=0) f[i][j][t]+=f[i-1][j-1][t-A[i-1]]; } } } return f[n][k][target]; } };