文章目錄

• URL
• 題目
• 分析
• 源碼
• • DP動(dòng)態(tài)規(guī)劃
  • 矩陣快速冪
• 源碼概述
• 小結(jié)

URL

鏈接：https://leetcode-cn.com/problems/count-vowels-permutation/

---

題目

---

分析

---

源碼

DP動(dòng)態(tài)規(guī)劃

#include <stdio.h> #include <stdlib.h> #include <string.h>typedef long long LL;int countVowelPermutation(int n){/* 0.1 */long long mod = 1e9 + 7 ; //取模 避免數(shù)據(jù)過(guò)大long long ans = 0; //返回值 存儲(chǔ)最后所有的可能項(xiàng)的數(shù)量LL * dp = (LL *)malloc(sizeof(LL)*5); // 前一次計(jì)算數(shù)據(jù)LL * ndp = (LL *)malloc(sizeof(LL)*5); // 存儲(chǔ)當(dāng)前次計(jì)算數(shù)據(jù)/* a , e , i , o , u *//* 0 , 1 , 2 , 3 , 4 *//* 1.1 *//* n = 1 */for (int i = 0;i < 5 ; i++){dp[i] = 1;}/* 1.2 *//* n >= 2 */for (int i=2;i<=n;i++){ // Tip : i <= n/* 1.3 *//* e , u , i + a */ndp[0] = (dp[1] + dp[2] + dp[4]) % mod; // n >= 2時(shí)，以各個(gè)元音結(jié)尾的數(shù)量(n為i的時(shí)候的數(shù)據(jù))/* a , i + e */ndp[1] = (dp[0] + dp[2]) % mod;/* e , o + i */ndp[2] = (dp[1] + dp[3]) % mod;/* i + o *///ndp[3] = (dp[2]) % mod;ndp[3] = dp[2]; //Tip : it is already been calculated by mod/* i , o + u */ndp[4] = (dp[2] + dp[3]) % mod;/* 1.4 */memcpy(dp , ndp , sizeof(LL)*5 ); // 將當(dāng)前次各個(gè)數(shù)量賦值給下一次待計(jì)算的數(shù)值變量}/* 2.1 */for (int i =0 ;i < 5 ;i++){ans = ( ans + dp[i]) % mod;}/* 0.2 */free(dp);free(ndp);return ans; }int main() {int n = 0;int ans = 0;n = 1; // -> 5ans = countVowelPermutation(n);printf("n = %d , len = %d\n",n,ans);n = 2; // -> 10ans = countVowelPermutation(n);printf("n = %d , len = %d\n",n,ans);n = 5; // -> 68ans = countVowelPermutation(n);printf("n = %d , len = %d\n",n,ans);return 0; }

矩陣快速冪

略

---

源碼概述

dp動(dòng)態(tài)規(guī)劃

計(jì)算每一個(gè)字符的前一個(gè)字符可能的組合情況

對(duì)每一個(gè)字母的符合的狀態(tài)做動(dòng)態(tài)規(guī)劃，即將前一種狀態(tài)累加到當(dāng)前狀態(tài)中

將上述的情況做 加法 ， 得到最終總的組合數(shù)量

矩陣快速冪

略

---

小結(jié)

dp動(dòng)態(tài)規(guī)劃

將當(dāng)前字符當(dāng)做最后一個(gè)字符分析，得到前一個(gè)字符的可能情況

從前一個(gè)狀態(tài)分析得到當(dāng)前狀態(tài)，得到動(dòng)態(tài)規(guī)劃遞推公式

匯總每一種分情況的數(shù)據(jù)，得到總的數(shù)據(jù)。

矩陣快速冪

略

總結(jié)

以上是生活随笔為你收集整理的【leetcode_1220】【困难】count-vowels-permutation / 统计元音字母序列的数目的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。