我如何记住这个程序？

Question

You are given a number n.

You are required to print the number of binary strings of length n with no consecutive 0's.

我的代码：

void solve(int n ,string ans  , vector<string> &myAns){
  if(ans.size()==n) {
    //cout << ans << "\n";
    myAns.push_back(ans);
    return;
  }
  if(ans.back() == '0'){
    solve(n , ans + "1" , myAns);
  }
  else{
    solve(n , ans + "0" , myAns);
    solve(n , ans + "1" , myAns);
  }
}

我应该如何将重复出现的字符串存储在哈希或其他东西中？

Answer 1

首先，您不需要为此算法进行动态规划或递归。您可以简单地使用下面的（请注意，这是第一个草图，可能存在更有效的解决方案）：

  size_t currentLength = 1;
  results_.push_back("0");
  results_.push_back("1");

  while(currentLength < length_)
  {
    size_t size = results_.size();  
    for(size_t i=0; i < size; i++)
    {
      string& elem = results_[i];
      if(elem.back() == '0')
      {
          elem.push_back('1');
      }
      else
      {
          results_.push_back(elem + "0");
          elem.push_back('1');
      }
    }
    currentLength = results_.back().size();
  }

如果您仍想记忆，则需要创建一个缓存，它是最简单形式的 std::map 或 std::unordered_map。通常你可以做的是从输入中创建一个唯一的键并保存 return 值。

Answer 2

请注意，您需要打印长度为 n 且没有连续 0 的二进制字符串的数量，而不是实际形成（并存储或打印）所有这些。

所以，是的，递归解决方案可以极大地受益于记忆，但不是所有的单个字符串。您应该存储的是每个长度的 number 个字符串。两个数字，实际上，一个字符串前面有一个1，另一个字符串前面有一个0。

long long solve(long long n, bool is_previous_a_zero = false)
{
    // Memoize the number of strings for each length and 
    // possible previous character.
    using key_t = std::pair<long long, bool>;
    static std::map<key_t, long long> mem{
        {{1, false}, 2},    // "0", "1"
        {{1, true}, 1}      // "1" after a "****0"
    };

    if ( n < 1 ) {
        return 0;
    }

    // First check if the result is already memoized.
    key_t key{ n, is_previous_a_zero };
    auto const candidate = mem.lower_bound(key);
    if( candidate != mem.cend()  and  candidate->first == key ) {
        return candidate->second;
    }

    // Otherwise evaluate it recursively and store it, before returning.
    long long result = is_previous_a_zero
                     ? solve(n - 1, false)
                     : solve(n - 1, true) + solve(n - 1, false);

    mem.emplace_hint(candidate, key, result);

    return result;
}

Here 此方法已针对所有最大 45 的长度进行测试。

请注意，如果您只对运行时效率感兴趣，您可以在编译时预先计算所有这些数字。

template< std::size_t N >
constexpr auto make_lut()
{
    std::array<long long, N + 1> lut{0, 2, 3};
    for ( size_t i = 3; i <= N; ++i) {
        lut[i] = lut[i - 1] + lut[i - 2];  // Yeah, it's a Fibonacci sequence.
    }
    return lut;
}

// Then it can be called like so
constexpr auto lut{ make_lut<45>() };

// The number of binary strings of length n with no consecutive 0's = lut[n];

你可以测试一下here。

要证明最后一个片段确实解决了发布的问题，请考虑以下几点：

只有 2 个可能的长度为 1 的二进制字符串："0" 和 "1".
有 3 个长度为 2 且没有连续的 0 的二进制字符串："01"、"10" 和 "11".
所有可能的长度为n的字符串是在所有长度为n - 1的字符串前加一个"1"组成的所有字符串加上所有组成的字符串将 "01" 添加到所有长度为 n - 2 的字符串。任何其他组合都会导致连续的零。

我如何记住这个程序？

How do I memoize this program?

c++

algorithm

dynamic-programming