动态规划之三—— 从暴力递归到动态规划_数字字符串转字母字符串

题目：

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

题目分析：

根据题目描述可知：数字1～26 是有对应的字母与之对应的，但超过26的数字无法给出对应字母，表明给出的是一个无效字符。对于数字0，比较特殊，当它单独出现的时候，没有与之对应的字母，但是它的前面是1 或者2 时，合并组成的两位数10 和20 是有可以转化成对应字母的，当然大于2后（30 >26）又为无效。

思路：

1.逐一遍历字符串， 当遍历到最后一个字符时，即完成一次转化。

2.当str[index] == '0'  时， 即表明出现无效字符。因为‘0’ 不可单独出现，一定是作为两位数中的个位数参与判断。

3. 当str[index] != '0' 时判断下一个字符

4. 当str[index+1] 没有越界，并且str[index] 与 str[index+1] 组成的两位数没有超过26， 则两这两个字符合并后，继续判断str[index+2];

5. 步骤1 和步骤2 即为递归的base case

代码实现：

//代码段1
#include <iostream>
#include <string>

using namespace std;

int process(string& str, int index){
    if(index == str.lenght()){
        return 1;
    }
    if(str[index] == '0'){
        return 0;
    }

    int way = process(str, index+1);
    if(index+1 < str.length() && (str[index]-'0')*10 - str[index+1]-'0' < 27){
        way += process(str, index+2);
    } 
    return way;
}
int number(string& str){
    if(str.length() == 0)
    {
        return 0;
    }
    return process(str, 0);
}
int main(){

    string str = "112";
    cout << "number: " << number(str) << endl;
    return 0;
}

运行结果：

优化为动态规划：

将递归过程改写为动态规划表来实现。

思路：

1.  分析递归函数的可变参数，发现只有index一个， 所以动态规划表是1维的，即动态规划表只与index有关。

2. 因为递归的base case中，迫使递归结束原因是 index == 字符数组长度值N，且表示完成1次转化，所以动态规划表dpArr 的大小为N+1,  且dpArr[N] = 1;

3. 通过已知的dpArr[N] ，从N到0， 依次填写动态规划表，即将调用递归函数的地方改为调用动态规划表dpArr

4. 动态规划函数返回的是dpApp[0]；

代码实现:

#include <string>
#include <iostream>

using namespace std;

int dp(string& str){
    if(str.length() == 0) return 0;
    int N = str.length();
    int dpArr[N+1] = {0};
    
    dpArr[N] = 1;
    for(int i = N-1; i >= 0; i--){
        if(str[i] != '0'){
            int way = dpArr[i+1];
            if(i+1 < N && (str[i] - '0')*10 - str[i+1]-'0' >27){
                way += dpArr[i+2];
            }
            dpArr[i] = way;
        }
    }     
    return dpArr[0];
}

int main(){
    string str = "112"
    cout << "dp: " << dp(str) << endl;
    return 0;
}

运行结果：