algorithm - 有多少个长度为 n 的单词最多有 k 个连续的元音？

Question

有多少个长度为 n 的单词最多有 k 个连续的元音？

我们的字母表有 21 个辅音字母和 5 个元音字母。

请原谅我没有提供测试用例。我没有测试用例，因为这是给 friend 的电话面试问题。

我从早上开始就在解决这个问题，您的小小帮助可以挽救我的生命。 我知道问题陈述含糊不清，但如果您能提供一些关于此动态编程模式的提示。

我发现由于它是计数问题，我们可以做这样的事情 dp[i][j] = length of word i with j consecutive vowel 。 我不知道如何进一步进行。请帮助重现!

Answer 1

这是一个有效的动态规划实现:

#include <iostream>
#include <string.h>
using namespace std;

#define n 5
#define k 2

int arr[n][k + 1];

int fill(int index, int currK){
    if(arr[n][currK] != 0) return arr[n][currK];  //if already calculated
    if(index == n - 1) {                          //base case
        arr[index][currK] = 21 + (currK ? 5 : 0);
        return arr[index][currK];
    }
    
    //recursive condition and step
    if(currK == 0) arr[n][currK] = 21 * fill(index + 1, k);
    else arr[n][currK] = 5 * fill(index + 1, currK - 1) + 21 * fill(index + 1, k);
    return arr[n][currK];   
}

int main(){
    memset(arr, 0, sizeof(arr));
    cout<<fill(0, k)<<endl;

    return 0;
}

想法是有一个 matrix[n][k + 1]，其中 matrix[i][j] 存储一个单词大小 i 您使用了 k - j 连续元音的地方。