首页 文章

动态编程减少蛮力

提问于
浏览 次
4

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

给定一个只包含（ ; ， _ ）的字符串 . 问题是将字符串分成一个或多个表情符号并计算可能的分区数 . 每个表情符号必须是消息的子序列，并且消息的每个字符必须只属于一个表情符号 . 请注意，子序列不需要是连续的 . 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):  ;_ ;|; _____;
algorithm data-structures dynamic-programming

2 回答

  • 1

    我将描述一个O（n ^ 4）时间和空间动态编程解决方案（可以轻松改进以仅使用O（n ^ 3）空间），该解决方案最多可以工作n = 100左右 .

    如果由单个 ; 组成，则调用子序列"fresh" .

    如果它对应于表情符号，则调用子句“已完成” .

    如果它具有非零长度并且是表情符号的正确前缀，则调用子序列"partial" . （例如， ; ， ;_ 和 ;___ 都是部分子序列，而空字符串 _ ， ;; 和 ;___;; 则不是 . ）

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

    设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 ; 组成的字符串，它只需不到2秒并报告答案为0（可能是由于 long long 溢出） .

    回复于
  • 2

    这是一个相当简单的memoized递归，它立即返回一个66 ; s后跟66 _ s后跟66 ; s的答案 . 该函数有三个参数： i = index in the string ，_3886848_和 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
    回复于

相关问题