@@ -67,7 +67,7 @@ public static int rec(ArrayList<Integer> A, ArrayList<Integer> B, int target, in
6767 * @param A: An integer array.
6868 * @param target: An integer.
6969 */
70- public static int MinAdjustmentCost (ArrayList <Integer >A ,int target ) {
70+ public static int MinAdjustmentCost2 (ArrayList <Integer >A ,int target ) {
7171// write your code here
7272if (A ==null ||A .size () ==0 ) {
7373return 0 ;
@@ -121,5 +121,118 @@ public static int rec2(ArrayList<Integer> A, ArrayList<Integer> B, int target, i
121121
122122return min ;
123123 }
124+
125+ /*
126+ * SOLUTION 3 递归2：
127+ * Rec + memory.
128+ * 改进的递归版本
129+ * */
130+ /**
131+ * @param A: An integer array.
132+ * @param target: An integer.
133+ */
134+ public static int MinAdjustmentCost3 (ArrayList <Integer >A ,int target ) {
135+ // write your code here
136+ if (A ==null ||A .size () ==0 ) {
137+ return 0 ;
138+ }
139+
140+ int [][]M =new int [A .size ()][100 ];
141+ for (int i =0 ;i <A .size ();i ++) {
142+ for (int j =0 ;j <100 ;j ++) {
143+ M [i ][j ] =Integer .MAX_VALUE ;
144+ }
145+ }
146+
147+ // 首个数字可以取1-100
148+ int min =Integer .MAX_VALUE ;
149+ for (int i =1 ;i <=100 ;i ++) {
150+ min =Math .min (min ,rec3 (A ,target ,0 ,i ,M ));
151+ }
152+
153+ return min ;
154+ }
155+
156+ /*
157+ * 将当前值设置为x能求得的最小解
158+ * */
159+ public static int rec3 (ArrayList <Integer >A ,int target ,int index ,int x ,
160+ int [][]M ) {
161+ int len =A .size ();
162+ if (index >=len ) {
163+ // The index is out of range.
164+ return 0 ;
165+ }
166+
167+ if (M [index ][x -1 ] !=Integer .MAX_VALUE ) {
168+ return M [index ][x -1 ];
169+ }
170+
171+ int bas =Math .abs (x -A .get (index ));
172+ int min =Integer .MAX_VALUE ;
173+
174+ // 对下一个值尝试取1-100
175+ for (int i =1 ;i <=100 ;i ++) {
176+ // 下一个值的取值不可以超过abs
177+ if (index !=len -1 &&Math .abs (i -x ) >target ) {
178+ continue ;
179+ }
180+
181+ // 计算dif
182+ int dif =bas +rec3 (A ,target ,index +1 ,i ,M );
183+ min =Math .min (min ,dif );
184+ }
185+
186+ // Record the result.
187+ M [index ][x -1 ] =min ;
188+ return min ;
189+ }
124190
191+
192+ /*
193+ * SOLUTION 4：
194+ * DP
195+ * */
196+ /**
197+ * @param A: An integer array.
198+ * @param target: An integer.
199+ */
200+ public static int MinAdjustmentCost (ArrayList <Integer >A ,int target ) {
201+ // write your code here
202+ if (A ==null ||A .size () ==0 ) {
203+ return 0 ;
204+ }
205+
206+ // D[i][v]: 把index = i的值修改为v，所需要的最小花费
207+ int [][]D =new int [A .size ()][101 ];
208+
209+ int size =A .size ();
210+
211+ for (int i =0 ;i <size ;i ++) {
212+ for (int j =1 ;j <=100 ;j ++) {
213+ D [i ][j ] =Integer .MAX_VALUE ;
214+ if (i ==0 ) {
215+ // The first element.
216+ D [i ][j ] =Math .abs (j -A .get (i ));
217+ }else {
218+ for (int k =1 ;k <=100 ;k ++) {
219+ // 不符合条件
220+ if (Math .abs (j -k ) >target ) {
221+ continue ;
222+ }
223+
224+ int dif =Math .abs (j -A .get (i )) +D [i -1 ][k ];
225+ D [i ][j ] =Math .min (D [i ][j ],dif );
226+ }
227+ }
228+ }
229+ }
230+
231+ int ret =Integer .MAX_VALUE ;
232+ for (int i =1 ;i <=100 ;i ++) {
233+ ret =Math .min (ret ,D [size -1 ][i ]);
234+ }
235+
236+ return ret ;
237+ }
125238}