91. Minimum Adjustment Cost

Leave a comment

September 26, 2016 by oneOokay

好了ladder里面165个题目算是全部刷完了第一遍。

2/6/2016开始的算法班,口可口可,刷了有七个月。。。中间夹杂了爹妈过来过年,陪爹妈去玩,拔智齿,搬家,回国七七八八各种。

看看等第二遍刷的时候还记得多少。

网传是个“背包”问题:随便搜了点东西:以后有空看吧:

DP之背包问题+记忆递归:http://www.cnblogs.com/jmzz/archive/2011/07/05/2098630.html

背包问题总结:http://sighingnow.github.io/algorithm/backpack.html

这个我觉得写的挺好的,要是能够静下心来从他的第一个解法一直看到进化完成的第四个解法,应该差不多了吧,但是我只看了最后一个解法,咳咳。以后再看吧:http://www.cnblogs.com/yuzhangcmu/p/4153927.html

public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
if (A == null || A.size() == 0) {
return 0;
}
int length = A.size();
int[][] f = new int[length][101]; //f[i][j]表示把A中的第i个元素的值设置为j的时候,前i个元素(包含i)符合条件变换的cost。那为什么是101呢?题目说所有的数不超过100且为正数,那么j的值的范围应该为1-100, 所以循环中j从1开始,一直到100,加上不参加循环的0,一共101个数。其实也可以用100啦,那么f[i][j]就会变成把A中的第i个袁术的值设置为j+1的时候,前i个元素的总cost,理解起来稍微绕了一下.
for (int i = 0; i < length; i ++) {//从第一个元素开始
for (int j = 1; j < 101; j ++) {//把第i个元素的值设置为j的时候
f[i][j] = Integer.MAX_VALUE; //先把f[i][j]初始化为max value
if (i == 0) { //当正在处理第一个元素的时候
f[i][j] = Math.abs(A.get(i) – j); //f[0][j]的值跟前面没有关系,直接等于自身的值与j的差值
}else {
for (int k = 1; k <= 100; k ++) { //当处理到第i个元素的时候,要把第i个元素的值设为j,此时对于第i-1个元素重新从1-100进行判断。
if (Math.abs(k – j) > target){ //当把i个元素设为j的同时把第i-1个元素设为k,对第i-1个元素和第i个元素进行判断。若k-j大于target,则不符合条件
continue;
}
int diff = Math.abs(j – A.get(i)) + f[i – 1][k]; //此时的总的cost(diff)为:把第i个元素设为j的cost + 把第i-1个元素设为k的总cost。此时不需要考虑把i-1设为k之后,i-1是否还跟i-2符合条件,因为在之前的循环中,i-1已经被计算过了,就算不符合条件的话,那么f[i-1][k]的值会为Max,在下一步的取两者中的较小值中也不会被取到。
f[i][j] = Math.min(diff, f[i][j]); //取两者中的较小值
}}}}
int result = Integer.MAX_VALUE;
for (int i = 1; i <= 100; i ++) {
result = Math.min(result, f[length – 1][i]);
}
return result;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: