How do I memoize this program?-CodePudding

You are given a number n.

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

My code:

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);
  }
}

How should I store the recurring strings, in a hash or something?

CodePudding user response：

First and foremost, you don't need dynamic programming or recursion for this algo. You can simply use the below one (please note that this is a first sketch there might exist a more efficient solution):


void solve(vector<string>& results_, size_t length_);
{
  size_t currentLength = 1;
  results_.push_back("0");
  results_.push_back("1");

  while(currentLength < length_)
  {
    vector<string> vecToConcat{};
    vecToConcat.reserve(results_.size());
    for(string& elem : results_)
    {
      if(elem.back() == '0')
      {
          elem.push_back('1');
      }
      else
      {
          vecToConcat.push_back(elem   "0");
          elem.push_back('1');
      }
    }
    results_.insert(results_.end(), vecToConcat.begin(), vecToConcat.end());
    currentLength = results_.back().size();
  }
}

If you still want to memoize, you need to create a cache which is an std::map or an std::unordered_map in its simplest form. Usually what you can do is create a unique key from the inputs and save the return value. However I'm not sure if i's goin to be useful for you as your algo doesn't recalculate the same things.

CodePudding user response：

Note that you are required to print the number of binary strings of length n with no consecutive 0's, not to actually form (and store or print) all of them.

So, yes, a recursive solution could greatly benefit from memoization, but not of all the single strings. What you should store is the number of strings for each length. Two numbers, actually, one of the strings preceded by a 1 and one of those preceded by a 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 this approach is tested for all the lengths up to 45.

Note that if you are interested only in runtime efficiency you can just precalculate all those numbers at compile time.

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];

You can test it here.

To prove that the last snippet really solves the posted problem, consider theese points:

There are only 2 possible binary strings of length 1: "0" and "1".
There are 3 possible binary strings of length 2 with no consecutive 0's: "01", "10" and "11".
All the possible strings of length n are all the strings composed prepending a "1" to all the strings of length n - 1, plus all the strings composed prepending "01" to all the strings of length n - 2. Any other combination would result in consecutive zeroes.