给定两个正整数 N 和 N .任务是找到大小为n的数组的数量，这些数组可以形成：
null
- 每个元素的范围为[1，m]
- 所有相邻的元素都是这样的，其中一个元素将另一个元素分开，即元素A 我 分开 i+1 或者 i+1 分开 i+2 .
例如：
Input : n = 3, m = 3.Output : 17{1,1,1}, {1,1,2}, {1,1,3}, {1,2,1}, {1,2,2}, {1,3,1}, {1,3,3}, {2,1,1},{2,1,2}, {2,1,3}, {2,2,1}, {2,2,2},{3,1,1}, {3,1,2}, {3,1,3}, {3,3,1}, {3,3,3} are possible arrays.Input : n = 1, m = 10.Output : 10
我们试图在数组的每个索引处找到可能的值的数量。首先，在指数0处，所有值都可能从1到m。现在观察每个指数，我们可以得出其倍数或其因子。所以，预先计算并存储所有元素。因此，对于以整数x结尾的每个位置i，我们可以转到下一个位置i+1，数组以整数x的倍数或x的因子结尾。此外，x的倍数或x的因子必须小于m。
因此，我们定义了一个二维数组dp[i][j]，它是大小为i的可能数组（可除相邻元素）的个数，j是它的第一个索引元素。
1 <= i <= m, dp[1][m] = 1.for 1 <= j <= m and 2 <= i <= n dp[i][j] = dp[i-1][j] + number of factor of previous element less than m + number of multiples of previous element less than m.
以下是该方法的实施情况：
C++
// C++ program to count number of arrays // of size n such that every element is // in range [1, m] and adjacent are // divisible #include <bits/stdc++.h> #define MAX 1000 using namespace std; int numofArray( int n, int m) { int dp[MAX][MAX]; // For storing factors. vector< int > di[MAX]; // For storing multiples. vector< int > mu[MAX]; memset (dp, 0, sizeof dp); memset (di, 0, sizeof di); memset (mu, 0, sizeof mu); // calculating the factors and multiples // of elements [1...m]. for ( int i = 1; i <= m; i++) { for ( int j = 2*i; j <= m; j += i) { di[j].push_back(i); mu[i].push_back(j); } di[i].push_back(i); } // Initialising for size 1 array for // each i <= m. for ( int i = 1; i <= m; i++) dp[1][i] = 1; // Calculating the number of array possible // of size i and starting with j. for ( int i = 2; i <= n; i++) { for ( int j = 1; j <= m; j++) { dp[i][j] = 0; // For all previous possible values. // Adding number of factors. for ( auto x:di[j]) dp[i][j] += dp[i-1][x]; // Adding number of multiple. for ( auto x:mu[j]) dp[i][j] += dp[i-1][x]; } } // Calculating the total count of array // which start from [1...m]. int ans = 0; for ( int i = 1; i <= m; i++) { ans += dp[n][i]; di[i].clear(); mu[i].clear(); } return ans; } // Driven Program int main() { int n = 3, m = 3; cout << numofArray(n, m) << "" ; return 0; } |
JAVA
// Java program to count number of arrays // of size n such that every element is // in range [1, m] and adjacent are // divisible import java.util.*; class GFG { static int MAX = 1000 ; static int numofArray( int n, int m) { int [][]dp = new int [MAX][MAX]; // For storing factors. Vector<Integer> []di = new Vector[MAX]; // For storing multiples. Vector<Integer> []mu = new Vector[MAX]; for ( int i = 0 ; i < MAX; i++) { for ( int j = 0 ; j < MAX; j++) { dp[i][j] = 0 ; } } for ( int i = 0 ; i < MAX; i++) { di[i] = new Vector<>(); mu[i] = new Vector<>(); } // calculating the factors and multiples // of elements [1...m]. for ( int i = 1 ; i <= m; i++) { for ( int j = 2 * i; j <= m; j += i) { di[j].add(i); mu[i].add(j); } di[i].add(i); } // Initialising for size 1 array for // each i <= m. for ( int i = 1 ; i <= m; i++) dp[ 1 ][i] = 1 ; // Calculating the number of array possible // of size i and starting with j. for ( int i = 2 ; i <= n; i++) { for ( int j = 1 ; j <= m; j++) { dp[i][j] = 0 ; // For all previous possible values. // Adding number of factors. for (Integer x:di[j]) dp[i][j] += dp[i - 1 ][x]; // Adding number of multiple. for (Integer x:mu[j]) dp[i][j] += dp[i - 1 ][x]; } } // Calculating the total count of array // which start from [1...m]. int ans = 0 ; for ( int i = 1 ; i <= m; i++) { ans += dp[n][i]; di[i].clear(); mu[i].clear(); } return ans; } // Driver Code public static void main(String[] args) { int n = 3 , m = 3 ; System.out.println(numofArray(n, m)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to count the number of # arrays of size n such that every element is # in range [1, m] and adjacent are divisible MAX = 1000 def numofArray(n, m): dp = [[ 0 for i in range ( MAX )] for j in range ( MAX )] # For storing factors. di = [[] for i in range ( MAX )] # For storing multiples. mu = [[] for i in range ( MAX )] # calculating the factors and multiples # of elements [1...m]. for i in range ( 1 , m + 1 ): for j in range ( 2 * i, m + 1 , i): di[j].append(i) mu[i].append(j) di[i].append(i) # Initialising for size 1 array for each i <= m. for i in range ( 1 , m + 1 ): dp[ 1 ][i] = 1 # Calculating the number of array possible # of size i and starting with j. for i in range ( 2 , n + 1 ): for j in range ( 1 , m + 1 ): dp[i][j] = 0 # For all previous possible values. # Adding number of factors. for x in di[j]: dp[i][j] + = dp[i - 1 ][x] # Adding number of multiple. for x in mu[j]: dp[i][j] + = dp[i - 1 ][x] # Calculating the total count of array # which start from [1...m]. ans = 0 for i in range ( 1 , m + 1 ): ans + = dp[n][i] di[i].clear() mu[i].clear() return ans # Driven Program if __name__ = = "__main__" : n = m = 3 print (numofArray(n, m)) # This code is contributed by Rituraj Jain |
C#
// C# program to count number of arrays // of size n such that every element is // in range [1, m] and adjacent are // divisible using System; using System.Collections.Generic; class GFG { static int MAX = 1000; static int numofArray( int n, int m) { int [,]dp = new int [MAX, MAX]; // For storing factors. List< int > []di = new List< int >[MAX]; // For storing multiples. List< int > []mu = new List< int >[MAX]; for ( int i = 0; i < MAX; i++) { for ( int j = 0; j < MAX; j++) { dp[i, j] = 0; } } for ( int i = 0; i < MAX; i++) { di[i] = new List< int >(); mu[i] = new List< int >(); } // calculating the factors and multiples // of elements [1...m]. for ( int i = 1; i <= m; i++) { for ( int j = 2 * i; j <= m; j += i) { di[j].Add(i); mu[i].Add(j); } di[i].Add(i); } // Initialising for size 1 array for // each i <= m. for ( int i = 1; i <= m; i++) dp[1, i] = 1; // Calculating the number of array possible // of size i and starting with j. for ( int i = 2; i <= n; i++) { for ( int j = 1; j <= m; j++) { dp[i, j] = 0; // For all previous possible values. // Adding number of factors. foreach ( int x in di[j]) dp[i, j] += dp[i - 1, x]; // Adding number of multiple. foreach ( int x in mu[j]) dp[i, j] += dp[i - 1, x]; } } // Calculating the total count of array // which start from [1...m]. int ans = 0; for ( int i = 1; i <= m; i++) { ans += dp[n, i]; di[i].Clear(); mu[i].Clear(); } return ans; } // Driver Code public static void Main(String[] args) { int n = 3, m = 3; Console.WriteLine(numofArray(n, m)); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program to count number of arrays // of size n such that every element is // in range [1, m] and adjacent are // divisible let MAX = 1000; function numofArray(n, m) { let dp = new Array(MAX); // For storing factors. let di = new Array(MAX); // For storing multiples. let mu = new Array(MAX); for (let i = 0; i < MAX; i++) { dp[i] = new Array(MAX); for (let j = 0; j < MAX; j++) { dp[i][j] = 0; } } for (let i = 0; i < MAX; i++) { di[i] = []; mu[i] = []; } // Calculating the factors and multiples // of elements [1...m]. for (let i = 1; i <= m; i++) { for (let j = 2 * i; j <= m; j += i) { di[j].push(i); mu[i].push(j); } di[i].push(i); } // Initialising for size 1 array for // each i <= m. for (let i = 1; i <= m; i++) dp[1][i] = 1; // Calculating the number of array possible // of size i and starting with j. for (let i = 2; i <= n; i++) { for (let j = 1; j <= m; j++) { dp[i][j] = 0; // For all previous possible values. // Adding number of factors. for (let x = 0; x < di[j].length; x++) dp[i][j] += dp[i - 1][di[j][x]]; // Adding number of multiple. for (let x = 0; x < mu[j].length; x++) dp[i][j] += dp[i - 1][mu[j][x]]; } } // Calculating the total count of array // which start from [1...m]. let ans = 0; for (let i = 1; i <= m; i++) { ans += dp[n][i]; di[i] = []; mu[i] = []; } return ans; } // Driver Code let n = 3, m = 3; document.write(numofArray(n, m)); // This code is contributed by rag2127 </script> |
输出：
17
时间复杂性： O（N*M）。
本文由 阿努伊·乔汉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
