[48无验证]字符编码-吉比特2018秋

1.题目描述

将a，b，c，d分别编码为1，0，10，11，那么给定一个二进制串就可以对其进行解码。例如二进制串“10”可以解码为“ab”，也可以解码为“c”。给定一个二进制串，要求计算出该二进制串有多少种解码方式。（二进制串的长度不超过45，能设计出O(n)复杂度的算法更佳）

2.题目解析

• 思路1：使用分治的思想
  基本思路是将原二进制串划分成两个规模更小的子串，求出对应的方案数，然后相乘，就可得到原串的方案数。但这里需要注意一下，因为“10”有两种解码方案（“11”的情况类似），所以划分子串时，如果中间恰好是“10”，则存在两种划分方案。
  例如：“xxx10yyy”
  划分方案一：“xxx1”和“0yyy”
  划分方案二：“xxx”、“10”和“yyy”
  两种方案数之和为最终的方案数。
• 思路2：
  使用动态规划的思想
  假设f(i)表示前面i个字符组成的二进制串对应的解码方案数，现在考虑第i-1个字符和第i个字
  符在如下四种情况下f(i)与f(i-1)的关系。
  xxxx00，00只有一种解码方案：xxxx00，所以f(i)=f(i-1)
  xxxx01，01只有一种解码方案：xxxx01，所以f(i)=f(i-1)
  xxxx10，10有两种解码方案：xxxx10和xxxx10，所以f(i)=f(i-1)+f(i-2)
  xxxx11，11有两种解码方案：xxxx11和xxxx11，所以f(i)=f(i-1)+f(i-2)

3.参考答案

• 分治

#include <iostream>
using namespace std;
int solve(int s, int e,string& str) {
  if (s >= e)
    return 1;
  int mid = (s + e) / 2;
  if (str[mid] == '1') { // 有两种解决方案
    return solve(s, mid,str) * solve(mid + 1, e,str) +
           solve(s, mid - 1,str) * solve(mid + 2, e,str);
  }else{ // 有一种解决方案
    return solve(s, mid,str) * solve(mid + 1, e,str);
  }
}
int main(){
  string str;
  cin >> str;
  printf("%d\n",solve(0,str.size()-1,str));
}

• 动态规划

#include <iostream>
using namespace std;
int solve(int idx,string& str){
  if (idx == -1) return 1;
  if (idx == 0) return 1;
  if ('0' == str[idx-1]) { // 前一个数字是0,只有一种解决方案
    return solve(idx-1,str);
  } else { // 前一个数字是1,有两种解决方案
    return solve(idx-1,str) + solve(idx-2,str);
  }
}
int main(){
  string str;
  cin >> str;
  printf("%d\n",solve(str.size()-1,str));
}