【划分型DP-最优划分】力扣LCR 165. 解密数字

现有一串神秘的密文 ciphertext，经调查，密文的特点和规则如下：

密文由非负整数组成
数字 0-25 分别对应字母 a-z
请根据上述规则将密文 ciphertext 解密为字母，并返回共有多少种解密结果。

示例 1:
输入: ciphertext = 216612
输出: 6
解释: 216612 解密后有 6 种不同的形式，分别是 “cbggbc”，“vggbc”，“vggm”，“cbggm”，“cqgbc” 和 “cqgm”

动态规划

class Solution {
public:
    int crackNumber(int ciphertext) {
        std::string str = std::to_string(ciphertext);
        int n = str.size();
        vector<int> dp(n+1);
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            char curNum = str[i-1], lastNum = str[i-2];
            if(curNum >= '0' && curNum <= '5'){
                if(lastNum == '1' || lastNum == '2'){
                    dp[i] += dp[i-2];
                }
                dp[i] += dp[i-1];
            }
            else{
                if(lastNum == '1'){
                    dp[i] += dp[i-2];
                }
                dp[i] += dp[i-1];
            }
        }
        return dp[n];
    }
};

时间复杂度： O（N）
空间复杂度： O（N）

这道题和将字母翻译为数字的逻辑一样，我们只需要定义dp[i]为前i个字符组成的字符串所能解密的字母个数。由于ciphertext是int类型，我们用to_string函数转化为string类型。然后我们开始遍历i，以第i个字符和第i-1个字符进行讨论，当curNum是0-5之间的时候，并且lastNum是1或2，我们可以将他们两个数字转化为一个字符。我们也可以将curNum自己转化为一个字母。

如果curNum是其他数字，那么只有当lastNum为1的时候，这两个数字才能转化为一个字母。或者我们也可以将curNum自己转化为一个字母。

最后返回dp[n]即可。

原文地址：https://blog.csdn.net/sjsjs11/article/details/143726225

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！