假设现在需要对一串数字字符串进行解码,我们知道该字符串的编码规则是
1->A
2->B
...
26->Z
输出数字N 代表有多少种可能的结果
encode = input().strip() def insert_incep(s,count): #final char if len(s) == 1 and s != '0': count.append(1) #left 2 char elif len(s) == 2: if 0 < int(s) <= 26 and (s[0] == '0'&nbs***bsp;s[1] == '0'): count.append(1) elif 0 < int(s) <= 26: count.append(2) elif int(s) > 26 : count.append(1) else: if int(s[0:2]) <= 26 and (s[0] != '0' and s[1] != '0'): insert_incep(s[2:],count) insert_incep(s[1:],count) else : insert_incep(s[1:],count) count = [] insert_incep(encode,count) print(sum(count))
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String num; while((num = br.readLine()) != null){ System.out.println(numDecodings(num)); } } // 动态规划求解 private static int numDecodings(String s) { if(s.length() == 0 || s.charAt(0) == '0') return 0; int dp[] = new int[s.length() + 1]; dp[0] = 1; dp[1] = 1; for(int i = 2; i <= s.length(); i++){ // 先考虑一位数的状态转移 if(s.charAt(i - 1) != '0') dp[i] += dp[i - 1]; // 再考虑两位数的状态转移 if(Integer.valueOf(s.substring(i - 2,i)) >= 10 && Integer.valueOf(s.substring(i - 2,i)) <= 26){ dp[i] += dp[i - 2]; } } return dp[s.length()]; } }
s = input() n = len(s) dp = [0] * (n+2) dp[0] = dp[1] = 1 for i in range(n): if '1' <= s[i] <= '9': dp[i+2] += dp[i+1] if i > 0 and '10' <= s[i-1:i+1] <= '26': dp[i+2] += dp[i] print(dp[-1])
def F(d, curr): if len(curr) == 0&nbs***bsp;len(curr) == 1 and curr[0]!=0: return 1 count = 0 if curr[0] != 0: count = F(d,curr[1:]) temp = curr[0]*10+curr[1] if temp < 27: count += F(d,curr[2:]) return count alpha = [chr(x) for x in range(ord('a'), ord('z') + 1)] d = {i+1:j for i, j in enumerate(alpha)} n = int(input()) strN = [int(i) for i in str(n)] print(F(d,strN))
#include<iostream> #include<string.h> using namespace std; int main() { char num[1024]; cin >> num; int nk[20] = { 1, 1 }; for (int i = 2; i < 20; i++) nk[i] = nk[i - 1] + nk[i - 2]; int len = strlen(num); int ans = 1; for (int i = 0; i < len; i++) { int j = i; while (j < len && (num[j] == '1' || num[j] == '2')) j++; if (j == len) { ans = ans*nk[j-i]; break; } if (num[j] == '0') { ans = ans*nk[j -i-1]; i = j; continue; } if (num[j] > '6') { if (num[j - 1] == '1') { ans = ans*nk[j - i + 1]; i = j; continue; } else if (num[j - 1] == '2') { ans = ans*nk[j - i]; i = j; continue; } else { i = j; continue; } } ans = ans*nk[j - i + 1]; i = j; } cout << ans << endl; return 0; }
s = input() dp = [0 for i in range(len(s) + 1)] dp[0] = 1 dp[1] = 1 if s[0] != "0" else 0 for i in range(2, len(s) + 1): dp[i] = dp[i - 1] if s[i - 1] != "0" else 0 if s[i - 2] == "1"&nbs***bsp;(s[i - 2] == "2" and s[i - 1] <= "6"): dp[i] += dp[i - 2] print(dp[-1])
设定状态: f[i] 表示字符串前i位有多少种解码方案
状态转移方程:
初始化 f 数组为 0 若字符串中 s[i] 表示的阿拉伯数字在 1~9 范围内, f[i] += f[i-1] 若s[i-1]和s[i]连起来表示的数字在 10~26 范围内, f[i] += f[i-2] (若i==1, 则f[i] += 1)
边界: f[0] = 1
特判:
/** * 本参考程序来自九章算法,由 @ 提供。版权所有,转发请注明出处。 * - 九章算法致力于帮助更多中国人找到好的工作,教师团队均来自硅谷和国内的一线大公司在职工程师。 * - 现有的面试培训课程包括:九章算法班,系统设计班,算法强化班,Java入门与基础算法班,Android 项目实战班, * - Big Data 项目实战班,算法面试高频题班, 动态规划专题班 * - 更多详情请见官方网站:http://www.jiuzhang.com/?source=code */ public class Solution { public int numDecodings(String s) { if (s == null || s.length() == 0) { return 0; } int[] nums = new int[s.length() + 1]; nums[0] = 1; nums[1] = s.charAt(0) != '0' ? 1 : 0; for (int i = 2; i <= s.length(); i++) { if (s.charAt(i - 1) != '0') { nums[i] = nums[i - 1]; } int twoDigits = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0'; if (twoDigits >= 10 && twoDigits <= 26) { nums[i] += nums[i - 2]; } } return nums[s.length()]; } }