元音组会-动态规划

package huisu;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。 字符串 s 按 字典序排列
 * 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。
 */
/**
 * 长度为 i 且以第 j 个元音为结尾的字符串数量 = 长度为 i - 1 且以小于等于 j 元音为结尾的字符串数量的和

dp[i][j]保存的状态为 长度为 i 且以大于等于 j 元音为结尾的字符串数量的和

所以有状态转移方程

dp[i][j] =dp[i-1][j] +dp[i][j-1];

 */
public class countYuanyin {
    public static void main(String[] args) {
        int n=2;
        System.out.println(countVowelStrings(n));
    }
    public static int countVowelStrings(int n) {
        List<List<Character>> list=new ArrayList<>();
        char []s={'a','e','i','o','u'};
        if(n==0){
            return 0;
        }
        if(n==1){
            return 5;
        }
        int [][]dp=new int[n+1][5];
        dp[1][0]=1;
        dp[1][1]=2;
        dp[1][2]=3;
        dp[1][3]=4;
        dp[1][4]=5;
        for(int i=2;i<=n;i++){
            for(int j=0;j<5;j++){
                if(j==0){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=dp[i][j-1]+dp[i-1][j];
                }
            }
        }

        
        return dp[n][4];
    }
}