Minimum sum of multiplications of n numbers | Python3 program to find the minimum sum of multiplication of n numbers ; Used in recursive memoized solution ; function to calculate the cumulative sum from a [ i ] to a [ j ] ; base case ; memoization , if the partition has been called before then return the stored value ; store a max value ; we break them into k partitions ; store the min of the formula thus obtained ; return the minimum ; Driver code
import numpy as np NEW_LINE import sys NEW_LINE dp = np . zeros ( ( 1000 , 1000 ) ) NEW_LINE def sum ( a , i , j ) : NEW_LINE INDENT ans = 0 NEW_LINE for m in range ( i , j + 1 ) : NEW_LINE INDENT ans = ( ans + a [ m ] ) % 100 NEW_LINE DEDENT return ans NEW_LINE DEDENT def solve ( a , i , j ) : NEW_LINE INDENT if ( i == j ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ i ] [ j ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ j ] NEW_LINE DEDENT dp [ i ] [ j ] = sys . maxsize NEW_LINE for k in range ( i , j ) : NEW_LINE INDENT dp [ i ] [ j ] = min ( dp [ i ] [ j ] , ( solve ( a , i , k ) + solve ( a , k + 1 , j ) + ( sum ( a , i , k ) * sum ( a , k + 1 , j ) ) ) ) NEW_LINE DEDENT return dp [ i ] [ j ] NEW_LINE DEDENT def initialize ( n ) : NEW_LINE INDENT for i in range ( n + 1 ) : NEW_LINE INDENT for j in range ( n + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = - 1 NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 40 , 60 , 20 ] NEW_LINE n = len ( a ) NEW_LINE initialize ( n ) NEW_LINE print ( int ( solve ( a , 0 , n - 1 ) ) ) NEW_LINE DEDENT