考察动态规划

LeetCode原题：**********************

• LeetCode 翻译的范围为0～25

动态规划基本思路：

(参看y总（AcWing）)

DP问题：

• 状态表示： 1)集合：f[i]表示下标为i的str能表示的翻译数量 2)属性：数量
• 状态计算：如何划分，可以将此时的状态用之前的状态来计算 1）前两个字符可以一起翻译：f[i] = f[i-1] + f[i-2]

2. 前两个字符不能一起翻译：f[i] = f[i-1]

class Solution {
public:
    /*
        动态规划：f[i]
            1. 状态表示：f[i] 
                1）集合：表示长度为 i 的数字的翻译方法总数
                2）属性：数量
            2. 状态计算：
                1）翻译当前数字：f[i] = f[i-1]
                2）不翻译当前数字（前提：当前数字不大于2，否则只能翻译）：f[i] = f[i-1] + f[i-2]
    */
    // 滚动数组优化：f[i] 只和 f[i-1] 和 f[i-2] 有关

    int translateNum(int num) {
        if (num <= 0) return 1;

        string nums = to_string(num);
        //  初始化
        int f[2];
        f[0] = 1, f[1] = 1;

        for (int i = 2; i <= nums.length(); ++i) {
            int n = (nums[i-2] - '0') * 10 + (nums[i-1] - '0');
            int tmp = (n >= 10 && n <= 25) ? f[0] + f[1] : f[0];
            f[1] = f[0];
            f[0] = tmp;
        }

        return f[0];
    }
};

牛客原题描述：JZ46 把数字翻译成字符串

难点在于：翻译的范围变成1～26，此时 0 已经不能作为翻译的选项了，而含0的只有10，20能够正确翻译，其他情况，含0的，都是非法的。

class Solution {
  public:
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    int solve(string nums) {
        // nums可能含有0，但0没有对应的字母字符，所以无法译码，返回0；
        // 所以如果nums中含有0，则必须和前一个字符组成10(j)或20(t)一起译码才行，否则都无法译码。
        for (int i = 0; i < nums.length(); ++i) {
            if (nums[i] == '0') {
                if (i - 1 < 0) return 0; // 考虑nums为"0"或"05"此类形式
                string temp = nums.substr(i - 1, 2); // 获取0和前面一个字符的组合
                if (temp == "10" || temp == "20") continue;
                return 0;
            }
        }

        int f[3];
        f[0] = f[1] = 1;
        for (int i = 2; i <= nums.length(); ++i) {
            string temp = nums.substr(i - 2, 2);
            int n = (temp[0] - '0') * 10 + (temp[1] - '0');
            if (temp == "10" || temp == "20") {
                // 10和20只能组合在一起译码，且只有一种译码结果
                f[2] = f[0];
            } else if (n > 10 && n <= 26) {
                f[2] = f[1] + f[0];
            } else f[2] = f[1];
            f[0] = f[1];
            f[1] = f[2];
        }
        return f[1];
    }
};

😘😘😘😘😘

😘😘😘😘

😘😘😘

😘😘

😘