关于排列组合问题转化为数列递推求解

关于排列组合问题转化为数列递推求解
问题是这样的:n盏线形排列的路灯,每盏路灯有开或关两种状态,现规定,这n盏路灯中的任意相邻k盏不能同时熄灭,问有多少种不同的状态
也就是说,共有多少个n位01字串,满足字串中不出现n个0相邻
据说要转化为数列递推求解,
打错了
应该是
满足字串中不出现k个0相邻
coffeebeanery 1年前 已收到2个回答 举报
赞

让我笑 幼苗

共回答了23个问题采纳率：82.6% 举报

设dp[i][j]表示符合条件的,长度为i,并且从最后一位开始向前直到1共有j个"0"的二进制串个数(比如,X...1000,j = 3,X...100,j = 2,X..1,j = 0)
即有:
dp[i][0] = dp[i-1][0]+dp[i-1][1]+..+dp[i-1][k-1]
dp[i][j] = dp[i-1][j-1] (1 =0

1年前

2

鼎湖飞龙安可乘 幼苗

共回答了66个问题 举报

an=a(n-1)+a(n-2)+……+a(n-k)
转化为k阶线性递推数列……
完毕

1年前

2
可能相似的问题

你能帮帮他们吗

精彩回答

Copyright © 2024 YULUCN.COM - 雨露学习互助 - 18 q. 0.023 s. - webmaster@yulucn.com