leetcode 困难题 1639. 通过给定词典构造目标字符串的方案数

Problem: 1639. 通过给定词典构造目标字符串的方案数动态规划的呢若words中每个单词的长度是m则对0-m之间的索引求出每个索引j内words[0][j], words[1][j]等的单词频次也就是arr数组dp[i][j]表示截止arr数组的i索引构成target[0-j]的方案数量初始化dp[i][0] 1不论m等于多少构成空字符串target的方案都只有1个递推公式的对dp[i][j]ch target[j-1] - ‘a’;若arr[i][ch] 0则要么从第i个索引选择一个字符target[j-1]target剩下的j-1个字符从words的索引0-i-1选择共dp[i-1][j-1] * arr[i][ch]种方案数量要么不选择第i个索引j个字符从0-i-1中选择共dp[i-1][j]种方案数量若arr[i][ch] 0则dp[i][j] dp[i-1][j];j个字符只从0-i-1中选择Codeclass Solution { public: vectorvectorint arr, dp; const int mod 1e9 7; int numWays(vectorstring words, string target) { int n words.size(), m words[0].size(); int mn target.size(), ch, r; arr.assign(m1, vectorint(26, 0)); for(int i 1; i n; i) { for(int j 1; j m; j) { arr[j][words[i-1][j-1] - a]; } } dp.assign(m 1, vectorint( mn 1, 0 )); for(int i 0; i m; i) dp[i][0] 1; for(int i 1; i m; i) { r min(mn, i); for(int j 1; j r; j) { ch target[j-1] - a; if(arr[i][ch] 0) { dp[i][j] (((long long)dp[i-1][j-1] * (long long)arr[i][ch])%mod dp[i-1][j])%mod; } else { dp[i][j] dp[i-1][j]; } } } return dp[m][mn]; } };