【算法】【递归与动态规划模块】数组字符串转字母的所有种数

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定一个都是数字组成的字符串，如果str中某个或者相邻的两个字符串数组组合后再1~26之间，说明可以组成一个字母，问，str字符串能够组成字母字符串的所有种数是多少？

如：
字符串：1111，可以组成AAAA，LAA,ALA,AAL,LL 一共是5种类型
字符串：0101，无法组成字母字符串，因此返回0
字符串：10，仅可以组成字母j，因此返回1

解决方案

原问题：
经典递归版本：
要素1: 入参为chars，索引i, 其中i代表截止到i，chars[0…i-1]已经排列完成，现在计算剩下的chars[i…chars.length-1]个数字的所有种数，f(chars, 0)即为答案
要素2：如果chars[i] 为 ‘0’ ，那么以chars[i]为开头的数字字符串无法形成字母字符串的，直接返回0
要素3：如果i == chars.length，返回1即可，说明前面的全部排列好，为1种。
要素4 ：如果chars[i]自己可以组成一个字母，那么res = chars[i]， res为当前状态的结果
要素4,：如果chars[i] 和chars[i+1] 能够合并组成一个字母，那么res += f(chars, i+2)
经典动态规划版本：
该版本是最常规的，容易理解但稍微判断复杂一些些的，也是本人自己想到的版本
dp[i] 表示截止到i. chars[0…i] 一共能够组成的字母数
dp[i] 递归表达式：
初始化种数dp[i]为0
1、首先计算如果不用chars[i]，前面的i-1个数字是否能够组成字母字符串，如果可以那么,判断chars[i]可以转字母的话，dp[i] += dp[i-1]
2、其次计算如果不用chars[i-1] 和 chars[i] 两个字母时，剩下的i-2个数字是否能够组成字母字符串，如果可以那么判断chars[i-1] 和 chars[i] 两个字母是否能够组成字母，能的话，dp[i] += dp[i-2]
反向动态规划版本：
该版本通过递归方式演化过来，递归只有一个变量，所以dp维度为1
dp[i]表示chars[0…i-1]已经排列完成，现在计算剩下的chars[i…chars.length-1]个数字的所有种数，dp[0]即为答案
dp[i] 首先至少为dp[i+1] , 通过递归中的要素4判断是否需要加上 dp[i+2] 即可

代码编写

java语言版本

原问题：
经典递归版本：

    /**
     * 二轮：递归方法
     * @param str
     * @return
     */
    public static int resCp1(String str) {
        if (str == null || str.length() == 0 || !checkIntegerStr(str)) {
            return 0;
        }
        char[] chars = str.toCharArray();
        return process1Cp(chars, 0);
    }

    private static int process1Cp(char[] chars, int i) {
        if (i == chars.length) {
            return 1;
        }
        if (chars[i] == '0') {
            // 以0开头的
            return 0;
        }
        int res = process1Cp(chars, i + 1);
        if (i+1 < chars.length && (chars[i] - '0') * 10 + (chars[i+1] - '0') < 27) {
            res += process1Cp(chars, i+2);
        }
        return res;
    }


    public static void main(String[] args) {
        System.out.println(resCp1("0101"));
    }
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方法（正向）
     * @param str
     * @return
     */
    public static int dpCp1ASC(String str) {
        if (str == null || str.length() == 0 || !checkIntegerStr(str)) {
            return 0;
        }
        char[] chars = str.toCharArray();
        int[] dp = new int[chars.length];
        dp[0] = chars[0] == '0' ? 0 : 1;
        for (int i = 1; i < chars.length; i++) {
            dp[i] = 0;
            // 首先去掉chars[i]前面是否能够形成
            if (dp[i-1] != 0) {
                // 前面的i-1个元素可以自成字母
                if (chars[i] != '0') {
                    dp[i] = dp[i-1];
                }
            }
            // 去掉i和i-1 两个数字剩下的是否能够组成？
            if (i-2 >= 0 && dp[i-2] != 0) {
                // 前面的能组成，那么现在只需要判断chars[i-1...i]是否能够组成字母即可
                if ((chars[i-1] - '0') * 10 + (chars[i] - '0') < 27) {
                    // 可以组成
                    dp[i] += dp[i-2];
                }
            }else if (i == 1 && chars[i-1] != '0') {
                // 这里要注意一下溢出情况需要考虑到第二个字符的特殊情况
                if ((chars[i-1] - '0') * 10 + (chars[i] - '0') < 27) {
                    // 可以组成
                    dp[i] += 1;
                }
            }
        }
        return dp[chars.length-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

反向动态规划版本:

    /**
     * 二轮：dp方法（反向）
     * @param str
     * @return
     */
    public static int dpCp1(String str) {
        if (str == null || str.length() == 0 || !checkIntegerStr(str)) {
            return 0;
        }
        char[] chars = str.toCharArray();
        int[] dp = new int[chars.length];
        dp[chars.length-1] = chars[chars.length - 1] == '0' ? 0 : 1;
        for (int i = chars.length - 2; i >= 0; i--) {
            if (chars[i] == '0') {
                dp[i] = 0;
                continue;
            }else {
                dp[i] = dp[i+1];
            }
            if (i+2 < chars.length && (chars[i] - '0') * 10 + (chars[i+1] - '0') < 27) {
                dp[i] += dp[i+2];
            }else if (i+2 == chars.length) {
                dp[i] += 1;
            }
        }
        return dp[0];
    }
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

c语言版本

正在学习中

c++语言版本