newcode 左边必有1的二进制字符串的数量

Difficulty
Medium
Tags
动态规划
URL
https://www.nowcoder.com/questionTerminal/5a04a774b9f54d9eb783a4d583e7a60a?page=1&onlyReference=false
Star
给定一个整数n，求由“0”字符和“1”字符组成的长度为n的所有字符串中，满足“0”字符的左边必有“1”字符的字符串的数量。
输入描述:
输入一行，包含一个整数n（）
输出描述:
输出一个整数，表示返回的答案，由于字符串的数量巨大，可能会溢出，请输出对取模后的答案。
注：程序员代码面试指南 P.294

法1 动态规划

思路
因为第 i 位的 选择 与前一位有关系：
  • 如果前一位为 0, 那么第i位只能是1
  • 如果前一位为 1， 那么第i位 0 1均可以
因此，定义状态:
dp[i][0] ：长度为 i 的 有效字符串 中以0结尾的个数
dp[i][1]：长度为 i的 有效字符串 中以1结尾的个数
显然，初始状态有 dp[0][1] = 1, dp[0][0] = 0
状态转移为: dp[i][0] = dp[i-1][1], dp[i][1] = dp[i-1][0] + dp[i-1][1]
题解
def solution(n:int) -> int:
	if n <= 1:
		return n
	dp = [[0] * 2 for _ in range(0, n+1)]
	dp[1] = [0, 1]
	dp[2] = [1, 1]
	
	for i in range(3, n+1):
		dp[i][0] = dp[i-1][1]
		dp[i][1] = sum(dp[i-1])
	return sum(dp[n])