Count L | C ++ program for the above approach ; Fumction to find the number of arrays of length L such that each element divides the next element ; Stores the number of sequences of length i that ends with j ; Initialize 2D array dp [ ] [ ] as 0 ; Base Case ; Iterate over the range [ 0 , l ] ; Iterate for all multiples of j ; Incrementing dp [ i + 1 ] [ k ] by dp [ i ] [ j ] as the next element is multiple of j ; Stores the number of arrays ; Add all array of length L that ends with i ; Return the resultant count ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int numberOfArrays ( int n , int l ) { int dp [ l + 1 ] [ n + 1 ] ; memset ( dp , 0 , sizeof dp ) ; dp [ 0 ] [ 1 ] = 1 ; for ( int i = 0 ; i < l ; i ++ ) { for ( int j = 1 ; j <= n ; j ++ ) { for ( int k = j ; k <= n ; k += j ) { dp [ i + 1 ] [ k ] += dp [ i ] [ j ] ; } } } int ans = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { ans += dp [ l ] [ i ] ; } return ans ; } int main ( ) { int N = 2 , L = 4 ; cout << numberOfArrays ( N , L ) ; return 0 ; }