Leetcode 题解 - 动态规划-分割整数12):分割整数构成字母字符串

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

26

[LeetCode] Decode Ways 解码方法

dp[n+1] 但是求接对应为位置是i-1 i是位置

还有就是10 100  0 这种情况 dp[i] = nums[i-1] == '0 '?  0 :  dp[i-1]

因为0的话不能考虑 把此处当成一个单独的字母存在 也就是和 前缀dp[i-1]无法配合这个字符形成字符串

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

 

这道题要求解码方法,跟之前那道 Climbing Stairs 爬梯子问题 非常的相似,但是还有一些其他的限制条件,比如说一位数时不能为0,两位数不能大于26,其十位上的数也不能为0,出去这些限制条件,根爬梯子基本没啥区别,也勉强算特殊的斐波那契数列,当然需要用动态规划Dynamci Programming来解。建立一位dp数组,长度比输入数组长多多2,全部初始化为1,因为斐波那契数列的前两项也为1,然后从第三个数开始更新,对应数组的第一个数。对每个数组首先判断其是否为0,若是将改为dp赋0,若不是,赋上一个dp值,此时相当如加上了dp[i - 1], 然后看数组前一位是否存在,如果存在且满足前一位不是0,且和当前为一起组成的两位数不大于26,则当前dp值加上dp[i - 2], 至此可以看出来跟斐波那契数组的递推式一样,代码如下:

这道题按爬梯子理解 比如226为例 3个数是由两个数后面加一个组成 或者1i个数后面加2个,那么就是2个数的可能性加1个数的可能性,就是dp[i - 1] + dp[i - 2]
 226
     i=0    1     2
     i=1    2     [2,2] [22]
     i=2    3     [2,2,6]  [22,6]  [2,26]

 

首先 先设定第一个是1 如果真实的S中 前一个(i-1)是0 那么我们就dp[i] = 0,否则说明i-1的个数存在,dp[i]起码有dp[i -1]个,再根据条件判断是不是要加dp[i -2]

注意这个if 判断条件:

i>1    && (       s.charAt(i-2) == '1'  ||   (s.charAt(i-2) == '2' && s.charAt(i-1) <= '6')            )
               

class Solution {public int numDecodings(String s) {int[] dp = new int[s.length()+1];dp[0] = 1;for(int i = 1; i < dp.length; i++){
//先加上dp[i-1]dp[i] = (s.charAt(i - 1) == '0') ? 0 : dp[i-1];
// dp[i-2]再加上多少if(i > 1 && (s.charAt(i-2) == '1' || (s.charAt(i-2) == '2' && s.charAt(i-1) <= '6'))){dp[i] += dp[i-2];}}return dp[s.length()];}
}

第二次写

class Solution {public int numDecodings(String s) {int n = s.length();int dp[] = new int[n+1];dp[0] = 1;for(int i = 1; i <= s.length(); i++){dp[i] = (s.charAt(i - 1) == '0') ? 0 : dp[i-1];if(i > 1 && (s.charAt(i - 2) == '1' ||(s.charAt(i-2) == '2' && s.charAt(i-1) <= '6'))){dp[i] += dp[i-2];}}return dp[n];}   
}