1641. Count Sorted Vowel Strings

我是找规律的...

func countVowelStrings(n int) int {
    f := []int{1, 1, 1, 1, 1}
    for ; n > 0; n-- {
        for i := 1; i < 5; i++ {
            f[i] += f[i-1]
        }
    }
    // fmt.Println(f)
    return f[4]
}

// f[2] = 1*5
// aa ae ai ao au
//    ee ei eo eu
//       ii io iu
//          oo ou
//             uu
// f[3] = 1*5+2*4+3*3+4*2+5*1
// f[4] = 1*5+(1+2)*4+(1+2+3)*3+(1+2+3+4)*2+f[3]*1

// f[1] = 1 0 0 0 0
// f[2] = `1 1 1 1 1 
// f[3] = 1 2 3 4 5
// f[4] = 1 3 6 10 15
// f[5] = 1 4 10 20 35
// f[6] = 1 5 

但其实比较容易往dp联想，但是我没想到。

n个数的方案和n-1的方案数是有关系的，但是需要比较细致的划分

比如n个数以a结尾的方案数，很容易想到是n-1个数以a结尾的方案数
而 n个数以u结尾的方案数，很容易想到是n-1个数以a结尾，以e结尾..以u结尾的方案数总和

设f[i][j] 表示i个数以j结尾的方案数

f[i][j] = sum(f[i][k]) k<=j