蛮力的动态规划约简

Question

表情符号由两个分号之间的任意正数下划线组成。因此，最短的表情符号是;_;。字符串;__;和;_____________;也是有效的表情图标。

给定一个只包含(;，_)表情的字符串，.The的问题是将字符串划分为一个或多个表情图标，并计算有多少个表情符号是可能的。每个表情必须是消息的子序列，并且消息的每个字符必须恰好属于一个表情。请注意，子序列不要求是连续的。subsequence definition。

我想到的方法是编写一个递归方法，如下所示：

countDivision(string s){
 //base cases
 if(s.empty()) return 1;
 if(s.length()<=3){
   if(s.length()!=3) return 0;
   return s[0]==';' && s[1]=='_' && s[2]==';';
 }
  result=0;
//subproblems
  genrate all valid emocticon and remove it from s let it be w
  result+=countDivision(w);
  return result;
}

当n很大时，例如100，上面的解决方案很容易超时。我应该使用哪种方法将这种暴力解决方案转换为动态编程解决方案？

几个例子

 1. ";_;;_____;" ans is 2
 2. ";;;___;;;" ans is 36

Example 1.

 ";_;;_____;" Returns: 2 
 There are two ways to divide this string into two emoticons. 
 One looks as follows:  ;_;|;_____; and the other looks like
 this(rembember we can pick subsequence it need not be contigous):  ;_ ;|; _____;

Answer 1

我将描述一个O(n^4)-time和-space动态编程解决方案(它可以很容易地改进为只使用O(n^3)个空间)，它应该可以工作到n=100左右。

如果一个子序列只包含一个;，则称其为"fresh“。

如果一个子序列对应于一个表情图标，则称其为“完成”。

如果子序列的长度不为零，并且是表情符号的正确前缀，则称其为“部分”。(例如，;、;_和;___都是部分子序列，而空字符串_、;;和;___;;不是。)

最后，如果子序列是新的、完成的或部分的，则称其为“可接受的”。

设f(i，j，k，m)是将字符串的前i个字符划分成精确j+k+m可容许子序列的方法数，其中恰好j是新的，k是部分的，m是完成的。请注意，有效分区到表情符号中的任何前缀都唯一地确定i，j，k和m --这意味着有效分区的前缀不会被超过一个元组(i，j，k，m)计数，所以如果我们可以保证，对于每个元组(i，j，k，m)，该元组中的分区前缀都被计数一次且只有一次，那么我们可以将元组的计数加在一起，得到一个有效的总数。具体地说，问题的答案将是f(n，0，j，0)的所有1 <= j <= n的和。

If s[i] = "_":
  f(i, j, k, m) =
    (j+1) * f(i-1, j+1, k, m-1)    // Convert any of the j+1 fresh subsequences to partial
    + m * f(i-1, j, k, m)          // Add _ to any of the m partial subsequences

Else if s[i] = ";":
  f(i, j, k, m) =
    f(i-1, j-1, k, m)              // Start a fresh subsequence
    + (m+1) * f(i-1, j, k-1, m+1)  // Finish any of the m+1 partial subsequences

我们还需要基本用例

f(0, 0, 0, 0) = 1
f(0, _, _, _) = 0
f(i, j, k, m) = 0 if any of i, j, k or m are negative

我自己的C++实现在几毫秒内给出了;;;___;;;的正确答案36，而对于;;;___;;;_;_;，它给出了540的正确答案(也是在几毫秒内)。对于一个由66个;s、66个_s和66个;s组成的字符串，它花费的时间不到2秒，并报告答案为0(可能是由于long long溢出)。

Answer 2

下面是一个相当简单的记忆递归，它会立即返回一个由66个;s和66个_s组成的字符串的答案。该函数有三个参数：i = index in the string、j = number of accumulating emoticons with only a left semi-colon和k = number of accumulating emoticons with a left semi-colon and one or more underscores。

还构建了一个数组，用于表示每个索引右侧有多少下划线和分号可用，以帮助确定下一个可能性。

复杂性是O(n^3)的，问题限制了搜索空间，其中j至多为n/2，k至多为n/4。

注释的JavaScript代码：

​

var s = ';_;;__;_;;';

// record the number of semi-colons and 
// underscores to the right of each index
var cs = new Array(s.length);
cs.push(0);

var us = new Array(s.length);
us.push(0);

for (var i=s.length-1; i>=0; i--){
  if (s[i] == ';'){
    cs[i] = cs[i+1] + 1;
    us[i] = us[i+1];
    
  } else {
    us[i] = us[i+1] + 1;
    cs[i] = cs[i+1];
  }
}

// memoize
var h = {};

function f(i,j,k){
  // memoization
  var key = [i,j,k].join(',');

  if (h[key] !== undefined){
    return h[key];
  }

  // base case
  if (i == s.length){
    return 1;
  }

  var a = 0,
      b = 0;
  
  if (s[i] == ';'){
    // if there are still enough colons to start an emoticon
    if (cs[i] > j + k){  
      // start a new emoticon
      a = f(i+1,j+1,k);
    }
      
    // close any of k partial emoticons
    if (k > 0){
      b = k * f(i+1,j,k-1);
    }
  } 
  
  if (s[i] == '_'){
    // if there are still extra underscores
    if (j < us[i] && k > 0){
      // apply them to partial emoticons
      a = k * f(i+1,j,k);
    }
    
    // convert started emoticons to partial
    if (j > 0){
      b = j * f(i+1,j-1,k+1);
    }
  }
  
  return h[key] = a + b;
}

console.log(f(0,0,0)); // 52

​