PROBLEM LINK:Author: Zi Song Yeoh DIFFICULTY:EASY PREREQUISITES:Dynamic Programming PROBLEM:Given a binary string with some characters replaced with question marks. Find the number of ways to replace the question marks with 1 or 0 so that the resulting string has exactly $k$ runs for all $1 \le k \le n$. EXPLANATION:Firstly, the naive solution is to iterate through all possible binary strings and find the number of runs in each of them. This solution will work in $O(2^{n} \cdot n)$ time. Now, to get a faster solution, we need dynamic programming. Let $dp[i][j][k]$ denote the number of ways to fill the question marks from digits $1$ to $i$ so that there are exactly $j$ runs and the $i$th digit is $k$. (so $k = 0$ or $1$) We can easily update the dp by considering all possible values of the current digit. If the $i$th digit can be $1$, then $dp[i][j][1] += dp[i  1][j  1][0] + dp[i  1][j][1]$. If the $i$th digit can be $0$, then $dp[i][j][0] += dp[i  1][j  1][1] + dp[i  1][j][0]$. The time complexity of this solution is $O(n^2)$. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. Tester's solution can be found here. RELATED PROBLEMS:asked 19 Dec '16, 09:54

Here is My solution . I solved it by kind of the same method .. but with less computations compared to the Tester's Solution. ( there was no need to make j < str.size() in the Tester's solution ... j<=i+1 will work as the number of runs cant be greater than the array size taken so far ) Solution Link https://www.codechef.com/viewsolution/15122646 Give a Thumbs up, If you like my solution :) answered 26 Aug '17, 21:25
