给定一个数N，想象只由0和1两种字符，组成的所有长度为N的字符串。如果某个字符串,任何0字符的左边都有1紧挨着,认为这个字符串达标。请问有多少达标的字符串？举例：
N=6
[1 0 1 0 1 0]
[1 0 1 0 1 1]
[1 0 1 1 0 1]
[1 0 1 1 1 0]
[1 0 1 1 1 1]
[1 1 0 1 0 1]
[1 1 0 1 1 0]
[1 1 0 1 1 1]
[1 1 1 0 1 0]
[1 1 1 0 1 1]
[1 1 1 1 0 1]
[1 1 1 1 1 0]
[1 1 1 1 1 1]
总共13种。
这道题是斐波那契数列。代码不用斐波那契数列，用递归最直观。
代码用golang编写，代码如下：
package main
import "fmt"
func main() {
for i := 1; i <= 10; i++ {
ret := ff(i)
fmt.Println(i, ret)
}
}
//一个一个试，最直观思维
func ff(n int) int {
ansval := 0
ans := &ansval
arr := make([]int, n)
//第0个位置，肯定是1
arr[0] = 1
process(arr, 1, ans)
return *ans
}
//递归
func process(arr []int, start int, ans *int) {
if start == len(arr) {
*ans++
return
}
if arr[start-1] == 1 {
arr[start] = 0
process(arr, start+1, ans)
}
arr[start] = 1
process(arr, start+1, ans)
}代码结果如下：
