算法|9.从暴力递归到动态规划2_规定1和a对应,2和b对应

9.算法|从暴力递归到动态规划2

1.数字字符串转英文字符串

题意：规定1和A对应、2和B对应、3和C对应…26和Z对应，那么一个数字字符串比如"111”就可以转化为:“AAA”、“KA"和"AK”
给定一个只有数字字符组成的字符串str，返回有多少种转化结果

解题思路：

• 边界判断1:能够不被阻挡的走到最后，说明这个决策正确，返回1
• 边界判断2:0不能单独存在，若存在，决策失误
• 普遍位置决策:单独转化必有，能不能拉下一个转换需要对它是不是存在以及存在之后和前边的结合在不在1~26之间这两个条件进行考察
• dp改写的时候普遍位置存在是在当前字符不是’0‘的基础上的。

核心代码：

递归代码：

public static int number(String str) {
    char[] s=str.toCharArray();
    if(s==null||str.length()==0){
        return 0;
    }
    return process(s,0);
}

public static int process(char[] str, int index) {
    if(index==str.length){
        return 1;
    }
    if(str[index]=='0'){
        return 0;
    }
    int ways=process(str,index+1);
    if(index+1<str.length&&(str[index]-'0')*10+str[index+1]-'0'<27){
        ways+=process(str,index+2);
    }
    return ways;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

dp代码：

public static int dp(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    char[] str = s.toCharArray();
    int N = str.length;
    int[] dp = new int[N + 1];
    dp[N] = 1;
    for (int i = N - 1; i >= 0; i--) {
        if(str[i]!='0'){
            int ways=dp[i+1];
            if(i+1<str.length&&(str[i]-'0')*10+str[i+1]-'0'<27){
                ways+=dp[i+2];
            }
            dp[i]=ways;
        }
    }
    return dp[0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

测试代码：略

测试结果：

累计和对半数组划分类问题

2.奇偶不敏感型

题意：给定一个正数数组arr，请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近，返回最接近的情况下，较小集合的累加和

解题思路：

• 主过程先将边界条件判断出来，和的一半计算出来

• 子过程边界条件注意：rest<0没有必要了，注意，这里要的是最小的累加和，所以i有效判断之后返回的值应该是当前下标的值，所以返回的值如果不有效的话，不能干扰结果（满足条件的最大值），所以我们设定为-1；相应的如果i==arr.length，说明中间没有阻挡，这条路是个有效决策，返回0即可

• 不超过rest说明当前已经求的是较小集合的累加和了，所以取的不是最小值，是满足条件的最大值！！！！！

• 改写dp的时候注意return 换成dp时，看是不是需要加else

• 改过之后，一次通过！！！！！！！！！（泰裤辣泰裤辣hhh）

• 

核心代码：

递归代码：

public static int right(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    int sum = 0;
    for (int cur : arr) {
        sum += cur;
    }
    return process(arr, 0, sum / 2);
}

public static int process(int[] arr, int i, int rest) {
    if (rest < 0) {
        return Integer.MAX_VALUE;
    }
    if (i == arr.length) {
        return 0;
    }
    int p1 = process(arr, i + 1, rest);
        int next = process(arr, i + 1, rest - arr[i]);
        if (next != -1) {
            int p2 = arr[i] + next;
            return Math.max(p1, p2);
        }
    return p1;
}
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

dp代码：

public static int dp(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    int sum = 0;
    for (int num : arr) {
        sum += num;
    }
    sum /= 2;
    int N = arr.length;
    int[][] dp = new int[N + 1][sum + 1];
    for (int i = N - 1; i >= 0; i--) {
        for (int rest = 0; rest <= sum; rest++) {
            int p1 = dp[i + 1][rest];
                int next = (rest - arr[i] < 0) ? -1 : dp[i + 1][rest - arr[i]];
                if (next != -1) {
                    int p2 = arr[i] + next;
                    dp[i][rest] = Math.max(p1, p2);
                } else {
                    dp[i][rest] = p1;
                }
        }
    }
    return dp[0][sum];
}
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

测试代码：略

测试结果：

3.奇偶敏感型

题意：给定一个正数数组arr，请把arr中所有的数分成两个集合，如果arr长度为偶数，两个集合包含数的个数要一样多；如果arr长度为奇数，两个集合包含数的个数必须只差一个请尽量让两个集合的累加和接近，返回最接近的情况下，较小集合的累加和。

解题思路：

• 相较于上题，本题需要多加一个可变参数，控制集合的个数，分为奇数情况和偶数情况
• 偶数情况只能是一半一半，没的说；
• 奇数要累计和最接近一半的那个（补集一定大于一半），但是此时这个最小集合的个数可能是奇数个也可能是偶数个，我们要个数和和都满足我们要求的小于和一般的最大值，重点理解这个最大值是怎么来的！！
• 可变参数增加，对应的dp表的维度也要增加一个，变成三维的了

核心代码：

递归代码：

public static int right(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    int sum = 0;
    for (int cur : arr) {
        sum += cur;
    }
    if ((arr.length & 1) == 0) {
        return process(arr, 0, arr.length / 2, sum / 2);
    } else {
        return Math.max(process(arr, 0, arr.length / 2, sum / 2), process(arr, 0, arr.length / 2 + 1, sum / 2));
    }
}

public static int process(int[] arr, int i, int picks, int rest) {
    if (rest < 0) {
        return -1;
    }
    if (i == arr.length) {
        return picks == 0 ? 0 : -1;
    }
    int p1 = process(arr, i + 1, picks, rest);
    int next = process(arr, i + 1, picks - 1, rest - arr[i]);
    if (next != -1) {
        int p2 = arr[i] + next;
        return Math.max(p1, p2);
    } else {
        return p1;
    }
}
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

dp代码：

public static int dp(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    int sum = 0;
    for (int num : arr) {
        sum += num;
    }
    sum /= 2;
    int N = arr.length;
    int M = (N + 1) / 2;
    int[][][] dp = new int[N + 1][M + 1][sum + 1];
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            for (int k = 0; k <= sum; k++) {
                dp[i][j][k] = -1;
            }
        }
    }
    for (int rest = 0; rest <= sum; rest++) {
        dp[N][0][rest] = 0;
    }
    for (int i = N - 1; i >= 0; i--) {
        for (int picks = 0; picks <= M; picks++) {
            for (int rest = 0; rest <= sum; rest++) {
                int p1 = dp[i + 1][picks][rest];
                int next = (rest - arr[i] < 0 || picks - 1 < 0) ? -1 : dp[i + 1][picks - 1][rest - arr[i]];
                if (next != -1) {
                    int p2 = arr[i] + next;
                    dp[i][picks][rest] = Math.max(p1, p2);
                } else {
                    dp[i][picks][rest] = p1;
                }
            }
        }
    }
    if ((arr.length & 1) == 0) {
        return dp[0][arr.length / 2][sum];
    } else {
        return Math.max(dp[0][arr.length / 2][sum], dp[0][(arr.length / 2) + 1][sum]);
    }
}
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

测试代码：略

测试结果：

4.最小路径和

题意：给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角
沿途只可以向下或者向右走，沿途的数字都累加就是距离累加和，返回最小距离累加和

解题思路：

• 递归代码注意尝试的方向

核心代码：

递归代码：

public static int minPathSum(int[][] m){
    if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
        return 0;
    }
    return process(m,m.length-1,m[0].length-1);
}

private static int process(int[][] m, int curR, int curC) {
    if(curC>=m[0].length||curR>=m.length){
        return 0;
    }
    if(curR==0&&curC==0){
        return m[0][0];
    }
    if(curR==0){
        return m[0][curC]+process(m,0,curC-1);
    }
    if(curC==0){
        return m[curR][0]+process(m,curR-1,0);
    }
    return m[curR][curC]+Math.min(process(m,curR-1,curC),process(m,curR,curC-1));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

dp代码：

public static int dp(int[][] m) {
    if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
        return 0;
    }
    int row = m.length;
    int col = m[0].length;
    int[][] dp = new int[row][col];
    dp[0][0] = m[0][0];
    for (int i = 1; i < row; i++) {
        dp[i][0] = dp[i - 1][0] + m[i][0];
    }
    for (int j = 1; j < col; j++) {
        dp[0][j] = dp[0][j - 1] + m[0][j];
    }
    for (int i = 1; i < row; i++) {
        for (int j = 1; j < col; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
        }
    }
    return dp[row - 1][col - 1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

测试代码：

// for test
public static int[][] generateRandomMatrix(int rowSize, int colSize) {
    if (rowSize < 0 || colSize < 0) {
        return null;
    }
    int[][] result = new int[rowSize][colSize];
    for (int i = 0; i != result.length; i++) {
        for (int j = 0; j != result[0].length; j++) {
            result[i][j] = (int) (Math.random() * 100);
        }
    }
    return result;
}

// for test
public static void printMatrix(int[][] matrix) {
    for (int i = 0; i != matrix.length; i++) {
        for (int j = 0; j != matrix[0].length; j++) {
            System.out.print(matrix[i][j] + " ");
        }
        System.out.println();
    }
}

public static void main(String[] args) {
    int rowSize = 10;
    int colSize = 10;
    int[][] m = generateRandomMatrix(rowSize, colSize);
    System.out.println(minPathSum(m));
    System.out.println(dp(m));

}
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

测试结果：

改不了dp的递归举例：贴纸问题(略)

题意：给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来返回需要至少多少张贴纸可以完成这个任务
例子：str= “babac”，arr = {“ba”,“c”,“abcd”}，ba + ba + c 3，abcd + abcd 2 abcd+ba 2，所以返回2

解题思路：

• 词频统计

核心代码：

递归代码：

public static int minStickers2(String[] stickers, String target) {
    int N = stickers.length;
    // 关键优化(用词频表替代贴纸数组)
    int[][] counts = new int[N][26];
    for (int i = 0; i < N; i++) {
        char[] str = stickers[i].toCharArray();
        for (char cha : str) {
            counts[i][cha - 'a']++;
        }
    }
    int ans = process2(counts, target);
    return ans == Integer.MAX_VALUE ? -1 : ans;
}

// stickers[i] 数组，当初i号贴纸的字符统计 int[][] stickers -> 所有的贴纸
// 每一种贴纸都有无穷张
// 返回搞定target的最少张数
// 最少张数
public static int process2(int[][] stickers, String t) {
    if (t.length() == 0) {
        return 0;
    }
    // target做出词频统计
    // target  aabbc  2 2 1..
    //                0 1 2..
    char[] target = t.toCharArray();
    int[] tcounts = new int[26];
    for (char cha : target) {
        tcounts[cha - 'a']++;
    }
    int N = stickers.length;
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < N; i++) {
        // 尝试第一张贴纸是谁
        int[] sticker = stickers[i];
        // 最关键的优化(重要的剪枝!这一步也是贪心!)
        if (sticker[target[0] - 'a'] > 0) {
            StringBuilder builder = new StringBuilder();
            for (int j = 0; j < 26; j++) {
                if (tcounts[j] > 0) {
                    int nums = tcounts[j] - sticker[j];
                    for (int k = 0; k < nums; k++) {
                        builder.append((char) (j + 'a'));
                    }
                }
            }
            String rest = builder.toString();
            min = Math.min(min, process2(stickers, rest));
        }
    }
    return min + (min == Integer.MAX_VALUE ? 0 : 1);
}
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

从左向右尝试模型总结2

dp改写规则：

• 进入嵌套的for循环后，看是不是需要加if判断条件。因为递归中是前边的边界判断完才能执行普遍位置的逻辑的，其实也相当于一个else分支，要记得判断！！！
• 贴纸问题改不了dp的递归原因：两个都是字符串长度/个数不确定，表的大小可能非常大，此时使用缓存表即HashMap

例题总结：

• 数字字符串转英文字符串:尝试策略——决策位置到头了没被挡，返回1；当前决策位置值为‘0’，之前的有问题，返回0；否则就是自己决策数量和拉上邻居决策的总数量。改dp注意：参数范围，初始方向
• 奇偶不敏感型累加和对半数组划分：rest<0;i==arr.length;next=-1；取的满足条件的最大值
• 奇偶敏感型累加和对半数组划分：rest<0;i==arr.length(picks);两个取的满足条件的最大值
• 最小路径和：尝试策略的方向倒着的，改成的dp是顺着的
• 贴纸问题：次品统计。改不了dp