算法练习（11）：牛客在线编程07 动态规划

package jz.bm;

import javax.crypto.MacSpi;
import java.util.ArrayList;
import java.util.Arrays;

public class bm7 {
    /**
     * BM62 斐波那契数列
     */
    public int Fibonacci(int n) {
        if (n <= 2) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    /**
     * BM63 跳台阶
     */
    public int jumpFloor (int number) {
        int[] dp = new int[number + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= number; i++) {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp[number];
    }

    /**
     * BM64 最小花费爬楼梯
     */
    public int minCostClimbingStairs (int[] cost) {
        int[] dp = new int[cost.length + 1];
//        dp[1] = 0; //只有一层已经在顶楼了
//        dp[2] = 0; //两层的话选择从2楼开始
        for (int i = 2; i <= cost.length; i++) {
            dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
        }
        return dp[cost.length];
    }

    /**
     * BM65 最长公共子序列(二)
     */
    public String LCS (String s1, String s2) {
        if (s1 == null || s1.equals("") || s2 == null || s2.equals("")) {
            return "";
        }
        int m = s1.length(), n = s2.length();
        String[][] dp = new String[m + 1][n + 1]; //dp[i][j]表示从左到右，当处理到s1的第i个元素和s2的第j个元素时的公共子序列
        for (int i = 0; i <= m; i++) {
            dp[i][0] = "";
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i] = "";
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1);
                } else {
                    //取长度较长的情况
                    dp[i][j] = dp[i - 1][j].length() > dp[i][j - 1].length() ? dp[i - 1][j] : dp[i][j - 1];
                }
            }
        }
        return dp[m][n].equals("") ? "-1" : dp[m][n];
    }

    /**
     * BM66 最长公共子串
     */
    public String LCS66 (String str1, String str2) {
        if (str1 == null || str1.equals("") || str2 == null || str2.equals("")) {
            return "";
        }
        int max = 0; //每段子串都是断开的，记录最长的那一个
        int maxIndex = 0;
        int m = str1.length(), n = str2.length();
        int[][] dp = new int[m + 1][n + 1]; //dp[i][j]表示从左到右，当处理到s1的第i个元素和s2的第j个元素时的公共字串长度
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > max) {
                        max = dp[i][j];
                        maxIndex = i;
                    }
                } else {
                    dp[i][j] = 0; //无法构成字串
                }
            }
        }
        return str1.substring(maxIndex - max, maxIndex);
    }

    /**
     * BM67 不同路径的数目(一)
     */
    public int uniquePaths (int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                //只有一行或一列时，只有一张方法
                if (i == 1) {
                    dp[i][j] = 1;
                    continue;
                }
                if (j == 1) {
                    dp[i][j] = 1;
                    continue;
                }
                //只能来自于上或者右
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }

    /**
     * BM68 矩阵的最小路径和
     */
    public int minPathSum (int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] dp = new int[row][col];
        //初值
        dp[0][0] = matrix[0][0];
        for (int i = 1; i < row; i++) {
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        }
        for (int i = 1; i < col; i++) {
            dp[0][i] = dp[0][i - 1] + matrix[0][i];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                //选择值最小的路径
                dp[i][j] = Math.min(dp[i - 1][j] + matrix[i][j], dp[i][j] + matrix[i][j]);
            }
        }
        return dp[row - 1][col - 1];
    }

    /**
     * BM69 把数字翻译成字符串
     */
    public int solve (String nums) {
        if (nums == null | "".equals(nums) || nums.startsWith("0")) {
            return 0;
        }
        int n = nums.length();
//        for (int i = 1; i < n; i++) {
//            if (nums.charAt(i) == '0' && !(nums.charAt(i - 1) == '1' || nums.charAt(i - 1) == '2')) {
//                return 0;
//            }
//        }
        int[] dp = new int[n + 1];
//        Arrays.fill(dp, 1);
        dp[0] = 1;  //默认一个才行
        dp[1] = nums.charAt(0) == '0' ? 0 : 1;
        for (int i = 2; i <= n; i++) {
            //无法独立编码也无法组合编码 00 或者 30 ，40 ...
            if(nums.charAt(i-1) == '0' && (nums.charAt(i-2) == '0' || nums.charAt(i-2) > '2')){
                return 0;
                //只能组合编码
            }else if(nums.charAt(i-1)=='0'){ //10,20
                dp[i] = dp[i-2];
                //只能独立编码
            }else if(nums.charAt(i-2)=='0' || nums.charAt(i-2)>'2' || nums.charAt(i-2)=='2'&& nums.charAt(i-1)>'6' ){ //0x,超过27
                dp[i] = dp[i-1];
                //两种编码方式都可以
            }else{
                dp[i] = dp[i-1]+dp[i-2];
            }
//            int num = (nums.charAt(i - 2) - '0') * 10 + nums.charAt(i - 1) - '0';
//            if ((num >= 11 && num <= 19) || (num >= 21 && num <= 26)) { //可以组合又可以单独译码
//                dp[i] = dp[i - 1] + dp[i - 2];
//            } else { //只能单独破译或者是10，20
//                dp[i] = dp[i - 1];
//            }
        }
        return dp[n];
    }

    /**
     * BM70 兑换零钱(一)
     */
    public int minMoney (int[] arr, int aim) {
        int[] dp = new int[aim + 1];
        //初值，都设为最大值，假设货币值1元，则最大数为aim，因此可以设置为aim + 1
        Arrays.fill(dp, aim + 1);
        dp[0] = 0;
        for (int i = 1; i <= aim; i++) {
            //枚举所有的面值，找到最小值
            for (int j = 0; j < arr.length; j++) {
                if (i - arr[j] >= 0) { //当前面值可用
                    dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1);
                }
            }
        }
        return dp[aim] > aim ? -1 : dp[aim];
    }
    /**
     * BM71 最长上升子序列(一)
     */
    public int LIS (int[] arr) {
        int m = arr.length;
        if (m == 0) {
            return 0;
        }
        int[] dp = new int[m]; //以i为结尾的最长子序列
        //初值都设置1，每个数字都是一个序列
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i = 1; i < m; i++) {
            //遍历之前的所有数字，找到子序列
            for (int j = 0; j < i; j++) {
                //小于结尾数字，序列长度加1
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(dp[i], res);
        }
        return res;
    }

    /**
     * BM72 连续子数组的最大和
     */
    public int FindGreatestSumOfSubArray (int[] array) {
        int n = array.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        int max = array[0];
        for (int i = 1; i <= n; i++) {
            dp[i] = Math.max(dp[i - 1] + array[i - 1], array[i - 1]);
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    /**
     * BM73 最长回文子串
     */
    public int getLongestPalindrome (String A) {
        int maxlen = 1;
        for(int i = 0; i < A.length() - 1; i++)
            maxlen = Math.max(maxlen, Math.max(getPalindrome(A, i, i), getPalindrome(A, i, i + 1)));
        return maxlen;
    }
    public int getPalindrome(String A, int left, int right) {
        while (left >= 0 && right < A.length() && A.charAt(left) == A.charAt(right)) {
            left--;
            right++;
        }
        //注意：长度要减1
        return right - left - 1;
    }

    /**
     * BM74 数字字符串转化成IP地址
     */
    //递归回溯
    public ArrayList<String> restoreIpAddresses (String s) {
        ArrayList<String> res = new ArrayList<>();
        dfs(s, 0, res, new ArrayList<String>());
        return res;
    }
    private void dfs(String s, int begin, ArrayList<String> res, ArrayList<String> cur) {
        //找到4段IP，并且字符串遍历完毕
        System.out.println(cur.size());
        if (cur.size() == 4 && begin == s.length()) {
            res.add(cur.get(0) + "." + cur.get(1) + "." + cur.get(2) + "." + cur.get(3));
            return;
        }
        //最多需要3 * （4 - cur.size())数字,最少需要（4 - cur.size()数字
        if ((s.length() - begin > 3 * (4 - cur.size())) || (s.length() - begin < (4 - cur.size()))) {
            return;
        }
        //寻找1到3位数字，作为当前的ip段
        for (int i = begin; i < begin + 3 && i < s.length(); i++) {
            String s1 = s.substring(begin, i + 1);
            int num = Integer.parseInt(s1);
            //小于255且不能有前导0
            if (num >= 0 && num <= 255 && (s1.length() == 1 || s1.charAt(0) != '0')) {
                cur.add(s1);
                dfs(s,i + 1, res, cur);
                cur.remove(cur.size() - 1);
            }
        }
    }

    /**
     * BM75 编辑距离(一)
     */
    public int editDistance (String str1, String str2) {
        int m = str1.length(), n = str2.length();
        int[][] dp = new int[m + 1][n + 1];//以i，j为结尾的字符串str1和str2，最少操作数
        //m为0时，str1变成str2最少操作数是str1插入字符
        for (int i = 1; i <= n; i++) {
            dp[0][i] = dp[0][i - 1] + 1;
        }
        //n为0时，str1变成str2最少操作数是str1删除字符
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i - 1][0] + 1;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                //不需要额外操作
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //插入、删除、修改都可以
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                }
            }
        }
        return dp[m][n];
    }

    /**
     * BM78 打家劫舍(一)
     */
    public int rob (int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++) {
            //偷这家，不偷这家
            dp[i] = Math.max(nums[i - 1] + dp[i - 2], dp[i - 1]);
        }
        return dp[n];
    }

    /**
     * BM79 打家劫舍(二)
     */
    public int rob2 (int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        //必须要分情况了
        //偷第一家,最后一家不可以偷
        dp[1] = nums[0];
        for (int i = 2; i < n; i++) {
            //偷这家，不偷这家
            dp[i] = Math.max(nums[i - 1] + dp[i - 2], dp[i - 1]);
        }
        int res = dp[n - 1];
        //不偷第一家
        Arrays.fill(dp, 0);
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            //偷这家，不偷这家
            dp[i] = Math.max(nums[i - 1] + dp[i - 2], dp[i - 1]);
        }
        return Math.max(res, dp[n]);
    }

    /**
     * BM80 买卖股票的最好时机(一)
     */
    public int maxProfit (int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;
        int res = 0;
        int min = prices[0];
        for (int i = 1; i < n; i++) {
            res = Math.max(prices[i] - min, res);
            min = Math.min(min, prices[i]);
        }
        return res;
    }

    /**
     * BM81 买卖股票的最好时机(二)
     */
    public int maxProfit1 (int[] prices) {
        int n = prices.length;
        if (n <= 1) return 0;
        int res = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] - prices[i - 1] > 0) {
                res += prices[i] - prices[i - 1];
            }
        }
        return res;
    }

    /**
     *
     */
}

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402