@@ -17,7 +17,7 @@ public static void main(String[] strs) {
1717 * @param A: An integer array.
1818 * @param target: An integer.
1919 */
20- public static int MinAdjustmentCost (ArrayList <Integer >A ,int target ) {
20+ public static int MinAdjustmentCost1 (ArrayList <Integer >A ,int target ) {
2121// write your code here
2222if (A ==null ) {
2323return 0 ;
@@ -26,6 +26,10 @@ public static int MinAdjustmentCost(ArrayList<Integer> A, int target) {
2626return rec (A ,new ArrayList <Integer >(A ),target ,0 );
2727 }
2828
29+ /*
30+ * SOL 1:
31+ * 最普通的递归方法。
32+ * */
2933public static int rec (ArrayList <Integer >A ,ArrayList <Integer >B ,int target ,int index ) {
3034int len =A .size ();
3135if (index >=len ) {
@@ -54,5 +58,68 @@ public static int rec(ArrayList<Integer> A, ArrayList<Integer> B, int target, in
5458
5559return min ;
5660 }
61+
62+ /*
63+ * 递归2：
64+ * Rec + memory.
65+ * */
66+ /**
67+ * @param A: An integer array.
68+ * @param target: An integer.
69+ */
70+ public static int MinAdjustmentCost (ArrayList <Integer >A ,int target ) {
71+ // write your code here
72+ if (A ==null ||A .size () ==0 ) {
73+ return 0 ;
74+ }
75+
76+ int [][]M =new int [A .size ()][100 ];
77+ for (int i =0 ;i <A .size ();i ++) {
78+ for (int j =0 ;j <100 ;j ++) {
79+ M [i ][j ] =Integer .MAX_VALUE ;
80+ }
81+ }
82+
83+ return rec2 (A ,new ArrayList <Integer >(A ),target ,0 ,M );
84+ }
85+
86+ public static int rec2 (ArrayList <Integer >A ,ArrayList <Integer >B ,int target ,int index ,
87+ int [][]M ) {
88+ int len =A .size ();
89+ if (index >=len ) {
90+ // The index is out of range.
91+ return 0 ;
92+ }
93+
94+ int dif =0 ;
95+ int min =Integer .MAX_VALUE ;
96+
97+ // If this is the first element, it can be from 1 to 100;
98+ for (int i =1 ;i <=100 ;i ++) {
99+ if (index !=0 &&Math .abs (i -B .get (index -1 )) >target ) {
100+ continue ;
101+ }
102+
103+ if (M [index ][i -1 ] !=Integer .MAX_VALUE ) {
104+ dif =M [index ][i -1 ];
105+ min =Math .min (min ,dif );
106+ continue ;
107+ }
108+
109+ B .set (index ,i );
110+ dif =Math .abs (i -A .get (index ));
111+ dif +=rec2 (A ,B ,target ,index +1 ,M );
112+
113+ min =Math .min (min ,dif );
114+
115+ // Record the result.
116+ M [index ][i -1 ] =dif ;
117+
118+ // 回溯
119+ B .set (index ,A .get (index ));
120+ }
121+
122+ return min ;
123+ }
57124
58125}