拥有域名后怎么建设网站,使用aspx做电影网站,自己怎么做游戏软件,网站备案协议前言#xff1a;最近在刷动态规划的算法题目#xff0c;感觉这一类题目还是有一点难度的#xff0c;但是不放弃也还是能学好的#xff0c;今天给大家分享的是牛客网中的编程题目[把数字翻译成字符串]#xff0c;这是一道经典的面试题目#xff0c;快手#xff0c;字节跳…前言最近在刷动态规划的算法题目感觉这一类题目还是有一点难度的但是不放弃也还是能学好的今天给大家分享的是牛客网中的编程题目[把数字翻译成字符串]这是一道经典的面试题目快手字节跳动等大厂出国这道题目。题目有点绕需要进行分类讨论最好配合画图工具进行理解这样能更好理解这道题目。一.题目二.进一步剖析题目1.关于动态规划思想动态规划算法的基本思想是将待求解的问题分解成若干个相互联系的子问题先求解子问题然后从这些子问题的解得到原问题的解对于重复出现的子问题只在第一次遇到的时候对它进行求解并把答案保存起来让以后再次遇到时直接引用答案不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。2.分析题目①分析题目能够译码的数字不会大于26即有效的译码范围为 [1,26]。②确定状态以数组 12345 为例首先要明确两点依题意可知数组中所有的数字都必须参与译码比如数组 1234 的某一种译码方式为 “1,2,3,4那么当数组尾再添加一个元素 5 时刚才的译码方式就会变为 1,2,3,4,5即 1,2,3,4 和 1,2,3,4,5 是同一种译码方式。 由于所有数字都要参与译码所以只要译码方式中存在个位数 0那么就都是无效的。当新加入一个数字5 时其除了可以单独作为一个数字参与译码外也可以与其左边的数字组成数字组合后再参与译码即 45 然后此时有多少种译码方式就取决于剩余的数字 即 123 了这和前面所说的是同一个道理只是此时把 4和5 看作是一个整体可以理解为原本数组 123 存在某种译码方式为 1,2,3现在加入 45译码方式就变成了 1,2,3,45。由于有效的译码范围为 [1,26]所以新加入的数字 5 只需要考虑与其左边的数字组成两位数组合无需再考虑组成更大的组合了比如三位数 345 等等。数字组合必须是十位数比如 0和2 组成的 02 也是不符合译码要求的。理解了上面两点后现在我们从数组 12345 的子串1开始分析然后逐步往后添加元素设数组 x 有 f(x) 种有效的译码方式当数组为 1 时有以下译码方式①1f(1)1接着加入数字2数组为 12 时有以下译码方式①12②12f(12)2其中第①种是从 数组 1 的译码方式 演变过来的就是在其基础上再加上单个数字 2。接着加入数字3数组为 123 时有以下译码方式①123②123③123f(123)3其中第①、②种是从 数组 12 的译码方式 演变过来的就是在其基础上再加上单个数字 3而第③种是从 数组 1 的译码方式 演变过来的就是在其基础上再加上数字组合 23。接着加入数字4数组为 1234 时有以下译码方式①1234②1234③1234④1234⑤1234其中第①、②、③种是从 数组 123 的译码方式 演变过来的就是在其基础上再加上单个数字 4而第④、⑤种是从 数组 12 的译码方式 演变过来的就是在其基础上再加上数字组合 34由于 45 不在有效译码的范围内所以这两种译码方式会被抛弃掉。f(1234)3可见数组 1234 的译码方式 是由 数组 123的译码方式 和 数组 12的译码方式 组成的。根据上面的分析当数组继续扩张到 12345 时那么其译码方式就为当新加入的数字 5 单独作为个位数参与译码时此时的译码方式 就等同于 数组 1234 的译码方式这组译码方式是有效的因为个位数 5 在有效的译码范围内而 5 与其前一位数字组成十位数 45 时此时的译码方式 就等同于 数组 123 的译码方式而这组译码是否有效则取决于 45 是否在有效的译码范围内。即 f(12345) f(12345 - 5) f(12345 - 45) f(1234) f(123) 33 6但是由于 45 不在有效的译码范围内所以 f(123) 的结果不能算在内所以最终结果应该为3。可见枚举到某位数字时此时有多少种译码方式可以由之前的译码方式相加得出即当前的状态可以利用之前的状态这是典型的动态规划。③状态转移方程f(x)f(x-1)f(x-2)其中 x 表示数组长度f(x) 表示有多少种有效的译码方式是否加上 f(x-1) 取决于 nums[x] 是否在 [1,9] 内即 nums[x] 需要满足不为0是否加上 f(x-2) 则取决于 nums[i-1] 与 nums[i] 的数字组合是否在 [10,26] 内时间复杂度O(N) 需要遍历一次数组空间复杂度O(N) 需要声明一个状态数组记录f(x)3.C代码class Solution {public:int solve(string nums) {// write code hereif(nums[0]0)return 0;vectorintdp(nums.size(),0);dp[0]1;for(int i1;idp.size();i){if(nums[i]!0){if(nums[i-1]1){dp[i]dp[i-1](i-20?dp[i-2]:1);continue;}if(nums[i-1]2(nums[i]-00nums[i]-07)){dp[i]dp[i-1](i-20?dp[i-2]:1);continue;} dp[i]dp[i-1]; }else {if(nums[i-1]-01||nums[i-1]-02){dp[i]dp[i-1];continue;}return 0; }}return dp[nums.size()-1];
}
};
