Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- //QUESTION - (PRINT BINARY STRING)
- //https://www.youtube.com/watch?v=nqrXHJWMeBc&list=PL-Jc9J83PIiG8fE6rj9F5a6uyQ5WPdqKy&index=18
- //recursive printing code
- void printBinaryString(int pos, string pathString, int &n){
- if(pos >= n){
- cout << pathString << '\n';
- return;
- }
- if(pathString.empty() || pathString[pos - 1] == '1'){
- printBinaryString(pos + 1, pathString + '0', n);
- }
- printBinaryString(pos + 1, pathString + '1', n);
- }
- //memo code
- // NOTE - Approach-
- /*
- To perform memoisation, we need to watch out for the params that are changing in the recursive code.
- Here for eg, Initially it would feel like the pos variable & pathString are changing.
- IMPORTANT - pos represents the bit for which the options are being explored (either 0 or 1)
- The pathString is changing and will be unique for each branch as we explored unique options to create a new branch.
- So we cannot memoise by memo(i, pathString) = given the ith position bit(pos) and pathString formed so far, how many valid binary strings.
- As this will not have any overlapping subproblems, because pathString for every state will be unique.(draw tree, easy)
- But analyse the code again:
- 1) pos is changing, and hence pos will be used as an identifier = memo(pos, ?)
- But pos alone is not enough to identify the overlapping subproblems here.
- for eg - pos = 2, 2 length binary string, we could have -
- 00, 01, 10, 11
- out of which 00 is invalid, so we are left with 01, 10, 11. These are all valid binary strings of length 2.
- Let's see for each, how many unique valid binary strings they are responsible for. The number of binary strings that they can form is equal to number of branches they can form. As each branch was explored only once and with unique option at that level, each branch will generate a unique string in the base case.
- memo(10) = 1 = this string has only one option to explore to, which is option '1', as the last char is 0, it cannot explore option '0'. It will explore create only 1 branch at level memo(10), and hence responsible for a single valid binary string
- memo(01) = 2 = this string has both options {0, 1}
- memo(11) = 2 = this string has both options {0, 1} as they both end with 1, and they could explore both options from their level {0, 1}. Both of these will explore both options, creating 2 branches that will futher lead to atleast 2 valid unique binary strings.
- so if we only take memo(pos) and define it as "every binary string of length 'pos' will generate the same amount of valid binary strings upto n" & these are overlapping subproblems, we can easily see that this is not the case, as count(01) = count(11) != count(10)
- 2) Ask yourself while looking at code below - Are we actually using pathString to make the decision?
- Why did we use pathString in the first place?
- Ans 2) As we are only generating valid cases, so if we are making the decision/exploring options for the current position 'pos', to avoid consecutive 0s, we need to make sure that we are exploring the option 0 for level 'pos' only if level 'pos - 1' has a 1, otherwise it will result in consecutive 0s.
- We maintained the pathString to check what the last character was, and on the basis of that we choose to explore option '0' for any level 'pos'.
- We are only checking the last character that if it is 0 or 1.
- So our memo identifiers would be = memo(pos, bit).
- And the possible states would be a mapping of this
- pos = {0, 1, 2, 3, ---- n - 1}
- bit = {0, 1}
- Define it as "every binary string of length 'pos' and last char 'bit' will generate the same amount of valid binary strings upto n" and the strings falling into a memo category will be classified as overlapping subproblems.
- so for above example pos = 2, valid binary string = 01, 10, 11
- memo(2, 0) = 10, string of length 2 ending with 0
- memo(2, 1) = 01, 11 , as both strings of length 2 ending with 1
- These are correctly overlapping as both 01, 11, will generate valid binary strings if continued up to n as they provide the same branching factor of 2 at their respective level, and hence they are correctly classified as the same problem getting solved twice by state memo(2, 1).
- So all in all, it depends on the position of bit in consideration, and if it ends with 0 or 1, which gives us information about how many branches it will created if the tree is extended up to the level n. So for n = 8, i = 3 and strings of length 1 ending with 1, which are {011, 101, 111} will be creating exactly same NUMBER/AMOUNT of branches, though unique binary strings. The number of branches will remain the same as branching factor will be equal for these strings.
- */
- int countBinaryString(int pos, string pathString, int &n, vector<vector<int> > &memo){
- if(pos >= n){
- return 1;
- }
- //memo[pos][last char in pathString]
- if(!pathString.empty() && memo[pos][pathString[pos - 1] - '0'] != 0){
- return memo[pos][pathString[pos - 1] - '0'];
- }
- int count = 0;
- if(pathString.empty() || pathString[pos - 1] == '1'){
- count += countBinaryString(pos + 1, pathString + '0', n, memo);
- }
- count += countBinaryString(pos + 1, pathString + '1', n, memo);
- return memo[pos][pathString[pos - 1] - '0'] = count;
- }
- // only last char passed, instead of whole binary string, because at every step we only check for the last char anyways
- int countBinaryStringRevised(int pos, int lastChar, int &n, vector<vector<int> > &memo){
- if(pos >= n){
- //we explored options for every position (so pos = n) at base case, and we always a valid binary string in base case, as we made only valid calls. If there were invalid calls while doing recursion, i.e. if we explored option '0' call from a level where last char was 0, we would have generated an invalid case, where strings of nature '00' might be there, and then we would have to filter it and return 1 for only the valid case.
- return 1;
- }
- //memo check
- if(lastChar != -1 && memo[pos][lastChar] != 0){
- return memo[pos][lastChar];
- }
- int count = 0;
- //option 0 for level pos
- if(pos == 0 || lastChar == 1){
- // only called if exploring option for 1st position OR last char was 1 at previous level/position (to avoid consecutive 0s)
- count += countBinaryStringRevised(pos + 1, 0, n, memo);
- }
- //option 1 for level pos
- count += countBinaryStringRevised(pos + 1, 1, n, memo);
- if(lastChar != -1){
- memo[pos][lastChar] = count;
- }
- return count;
- }
- int countBinaryStringDP(int &n){
- /*Storage and Meaning - dp[i][0] = about ith position bit out of n - 1 & string ending with 0
- dp[i][1] = about ith position bit out of n - 1 & string ending with 1
- dp[i][0] = count of valid binary strings of length (i) ending with 0
- dp[i][1] = count of valid binary strings of length (i) ending with 1
- */
- vector<vector<int> > dp(n, vector<int>(2, 0));
- /*
- Direction - smallest problem is at dp[0][0] and dp[0][1].
- */
- dp[0][0] = 1;
- dp[0][1] = 1;
- // Travel & Solve
- for(int i = 1; i < n; i++){
- dp[i][0] = dp[i - 1][1];
- dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
- }
- //Both these should be returned as these 2 cells mean
- // dp[n - 1][0] = binary strings of length n, that ends with 0
- // dp[n - 1][1] = binary strings of length n, that ends with 1
- // but both are valid binary strings of length n that have no consecutive 0s
- return dp[n - 1][0] + dp[n - 1][1];
- }
- int main() {
- // your code goes here
- int n;
- cin >> n;
- // printBinaryString(0, "", n);
- //vector<vector<int> > memo(n, vector<int> (2, 0));
- //cout << countBinaryStringRevised(0, -1, n, memo) << '\n';
- cout << countBinaryStringDP(n) << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
