Given two integers n and k, count the number of binary strings of length n where adjacent 1 appear k times. Since the answer can be huge, print it modulo 10^{9}+7.
Example 1:
Input:
n = 3 , k = 2
Output: 1
Explanation: Possible string is "111".
Example 2:
Input:
n = 5 , k = 2
Output: 6
Explanation: Possible strings are:
"00111" , "10111" , "01110"
"11100" , "11101" , "11011".
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function countStrings() which accepts integers n and k as input parameter and returns the number of binary strings that satisfy the given condition.
Expected Time Complexity: O(n*k).
Expected Auxiliary Space: O(n*k). 
Constraints:
1 <= n, k <= 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def countStrings(self, n, k): 

        # code here 



Solutions:
class Solution:

	def countStrings(self, n, k):
		dp = [[[0, 0] for __ in range(k + 1)] for _ in range(n + 1)]
		dp[1][0][0] = 1
		dp[1][0][1] = 1
		for i in range(2, n + 1):
			for j in range(k + 1):
				dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1]
				dp[i][j][1] = dp[i - 1][j][0]
				if j >= 1:
					dp[i][j][1] += dp[i - 1][j - 1][1]
		return (dp[n][k][0] + dp[n][k][1]) % 1000000007


class Solution:

	def countStrings(self, n, k):
		dp = [[[0, 0] for j in range(k + 1)] for i in range(n + 1)]
		dp[1][0][0] = 1
		dp[1][0][1] = 1
		for i in range(2, n + 1):
			for j in range(k + 1):
				dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1]
				dp[i][j][1] = dp[i - 1][j][0]
				if j >= 1:
					dp[i][j][1] += dp[i - 1][j - 1][1]
		return (dp[n][k][0] + dp[n][k][1]) % (10 ** 9 + 7)


class Solution:

	def countStrings(self, n, k):
		dp = [[0 for j in range(k + 1)] for l in range(n + 1)]
		dp[0][0] = 1
		m = 10 ** 9 + 7
		for i in range(n + 1):
			for j in range(min(i, k + 1)):
				if i == 0:
					continue
				if i == 1:
					dp[i][j] = 2
				elif j == 0:
					dp[i][j] = dp[i - 2][j] + dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 2][j] + dp[i - 1][j] + dp[i - 1][j - 1] - dp[i - 2][j - 1]
				dp[i][j] %= m
		return dp[-1][-1]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def countStrings(self, n, bitcount):
		if n < k:
			return 0
		table = [[[-1] * 2 for _ in range(n + 1)] for _ in range(n + 1)]

		def recursive(n, k, table, prev=0):
			if n == 0 and k == 0:
				return 1
			if n == 0:
				return 0
			if table[n][k][prev] > -1:
				return table[n][k][prev]
			if prev == 1:
				table[n][k][prev] = (recursive(n - 1, k - 1, table, prev=1) + recursive(n - 1, k, table, prev=0)) % 1000000007
			else:
				table[n][k][prev] = (recursive(n - 1, k, table, prev=1) + recursive(n - 1, k, table, prev=0)) % 1000000007
			return table[n][k][prev]
		return recursive(n, bitcount, table)