Для решения задачи с помощью динамического программирования задача должна обладать двумя существенными свойствами:
1. Перекрывающиеся подзадачи. Задача может быть разделена на более мелкие подзадачи, и решения этих подзадач перекрываются или многократно используются повторно во время вычислений. Это свойство позволяет нам избежать избыточных вычислений, сохраняя решения подзадач и повторно используя их при необходимости.
2. Оптимальная подструктура: оптимальное решение задачи может быть построено из оптимальных решений ее подзадач. Это свойство позволяет нам итеративно строить решение, начиная с базовых случаев и комбинируя решения меньших подзадач для получения оптимального решения исходной задачи.
Эти свойства позволяют нам применять методы динамического программирования, такие как запоминание или табулирование, для эффективного решения проблемы, избегая ненужных повторных вычислений и используя ранее вычисленные решения.
Редактировать проблему расстояния:
Проблема расстояния редактирования, также известная как расстояние Левенштейна, представляет собой измерение разницы между двумя строками. Он определяет минимальное количество операций, необходимых для преобразования одной строки в другую, где разрешенными операциями обычно являются вставки, удаления или замены отдельных символов.
Вот псевдокод рекурсивного решения с перекрывающимися вызовами и экспоненциальным временем.
editDistance(str1, str2):
// Base cases
if str1 is empty:
return length of str2
if str2 is empty:
return length of str1
if last characters of str1 and str2 are the same:
return editDistance(str1 without last character, str2 without last character)
// Recursive calls
return 1 + minimum of the following:
- editDistance(str1 without last character, str2) // Deletion
- editDistance(str1, str2 without last character) // Insertion
- editDistance(str1 without last character, str2 without last character) // Replacement
Решение для динамического программирования:
def editDistance(str1, str2):
m = len(str1)
n = len(str2)
# Create a 2D matrix to store the edit distances
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Initialize the first row and column of the matrix
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
# Fill in the remaining cells of the matrix
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] # No operation required
else:
dp[i][j] = 1 + min(dp[i - 1][j], # Deletion
dp[i][j - 1], # Insertion
dp[i - 1][j - 1]) # Substitution
# Return the minimum edit distance (bottom-right cell of the matrix)
return dp[m][n]
# Example usage
str1 = "kitten"
str2 = "sitting"
distance = edit_distance(str1, str2)
print("Edit distance between", str1, "and", str2, "is", distance)
Проблема отбрасывания яиц:
Задача о падении яиц — это классическая головоломка в математике и информатике, которая включает в себя определение минимального количества попыток, необходимых для нахождения самого высокого этажа, с которого яйцо может быть сброшено, не разбиваясь.
Вот псевдокод рекурсивного решения с перекрывающимися вызовами и экспоненциальным временем.
eggDrop(eggs, floors):
// Base cases
if floors == 0 or floors == 1:
return floors
if eggs == 1:
return floors
// Initialize minimum attempts to a large value
minAttempts = infinity
// Recursive calls
for i in range(1, floors + 1):
attempts = 1 + max(eggDrop(eggs - 1, i - 1), eggDrop(eggs, floors - i))
minAttempts = min(minAttempts, attempts)
return minAttempts
Решение для динамического программирования:
def egg_drop(num_eggs, num_floors):
# Create a 2D matrix to store the minimum attempts required
dp = [[0] * (num_floors + 1) for _ in range(num_eggs + 1)]
# Initialize the base cases
for i in range(1, num_eggs + 1):
dp[i][1] = 1 # If there's only one floor, one attempt is needed
dp[i][0] = 0 # If there are no floors, no attempts are needed
for j in range(1, num_floors + 1):
dp[1][j] = j # If there's only one egg, attempt all floors one by one
# Fill in the remaining cells of the matrix
for i in range(2, num_eggs + 1):
for j in range(2, num_floors + 1):
dp[i][j] = float('inf') # Set initial minimum attempts to infinity
for k in range(1, j + 1):
# Calculate the maximum of two possibilities:
# 1. Egg breaks -> Check below floors (i-1) eggs, (k-1) floors
# 2. Egg doesn't break -> Check above floors (i) eggs, (j-k) floors
# Add 1 for the current attempt
attempts = 1 + max(dp[i - 1][k - 1], dp[i][j - k])
# Update the minimum attempts if a better solution is found
if attempts < dp[i][j]:
dp[i][j] = attempts
# Return the minimum attempts (top-right cell of the matrix)
return dp[num_eggs][num_floors]
# Example usage
num_eggs = 2
num_floors = 10
min_attempts = egg_drop(num_eggs, num_floors)
print("Minimum attempts required to find the critical floor:",
min_attempts)
Целочисленная задача о рюкзаке:
Целочисленная задача о рюкзаке — это классическая задача оптимизации в математике и информатике, которая включает в себя максимизацию ценности или полезности предметов, упакованных в рюкзак, при соблюдении ограничений его веса или вместимости. Цель состоит в том, чтобы определить, какие предметы следует выбрать и упаковать в рюкзак, чтобы получить максимальную общую стоимость.
Псевдокод: рекурсивное решение с перекрывающимися вызовами и экспоненциальным временем.
knapsack(weight[], value[], capacity, n):
if n == 0 or capacity == 0:
return 0
if weight[n-1] > capacity:
return knapsack(weight, value, capacity, n-1)
else:
# Calculate the maximum value by either including or excluding the current item
include = value[n-1] + knapsack(weight, value, capacity - weight[n-1], n-1)
exclude = knapsack(weight, value, capacity, n-1)
return max(include, exclude)
Решение для динамического программирования:
def knapsack_max_value(weights, values, capacity):
n = len(weights)
# Create a 2D matrix to store the maximum values
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
# Fill in the matrix using a bottom-up approach
for i in range(1, n + 1):
for j in range(1, capacity + 1):
if weights[i - 1] <= j:
# Include the item and subtract its weight from the capacity
# Compare the value of including the item with excluding it
dp[i][j] = max(values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j])
else:
# Item weight exceeds current capacity, exclude the item
dp[i][j] = dp[i - 1][j]
# Return the maximum value (bottom-right cell of the matrix)
return dp[n][capacity]
# Example usage
weights = [3, 2, 4, 5]
values = [6, 8, 7, 10]
capacity = 9
max_value = knapsack_max_value(weights, values, capacity)
print("Maximum value that can be achieved:", max_value)
Самая длинная общая подпоследовательность:
Самая длинная общая подпоследовательность (LCS) — это понятие в информатике и математике, которое относится к самой длинной последовательности символов или элементов, которые имеют две или более строк или последовательностей.
Например, для строк «ABCD» и «ACDF» самой длинной общей подпоследовательностью будет «ACD», поскольку эти символы появляются в обеих строках и сохраняют свой относительный порядок.
Псевдокод рекурсивного решения с перекрывающимися вызовами и экспоненциальным временем.
longestCommonSubsequence(str1, str2, m, n):
if m == 0 or n == 0:
return 0
if str1[m-1] == str2[n-1]:
return 1 + longestCommonSubsequence(str1, str2, m-1, n-1)
else:
return max(longestCommonSubsequence(str1, str2, m-1, n), longestCommonSubsequence(str1, str2, m, n-1))
Решение для динамического программирования:
def longest_common_subsequence(str1, str2):
m = len(str1)
n = len(str2)
# Create a 2D matrix to store the lengths of the common subsequences
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Fill in the matrix using a bottom-up approach
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
# If characters match, increment the LCS length
dp[i][j] = dp[i - 1][j - 1] + 1
else:
# Characters don't match, take the maximum of LCS lengths
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# Trace back and construct the LCS string
lcs = ""
i, j = m, n
while i > 0 and j > 0:
if str1[i - 1] == str2[j - 1]:
# If characters match, add it to the LCS string
lcs = str1[i - 1] + lcs
i -= 1
j -= 1
elif dp[i - 1][j] > dp[i][j - 1]:
# Move to the cell with a larger LCS length
i -= 1
else:
j -= 1
# Return the LCS length and the LCS string
return dp[m][n], lcs
# Example usage
str1 = "AGGTAB"
str2 = "GXTXAYB"
length, lcs = longest_common_subsequence(str1, str2)
print("Length of Longest Common Subsequence:", length)
print("Longest Common Subsequence:", lcs)
Самая длинная общая подстрока:
Проблема самой длинной общей подстроки (LCS) — это понятие в информатике и обработке строк, которое включает в себя поиск самой длинной непрерывной подстроки, которая является общей для двух или более входных строк.
Псевдокод рекурсивного решения с перекрывающимися вызовами с экспоненциальным временем.
longestCommonSubstring(str1, str2, m, n, count):
if m == 0 or n == 0:
return count
if str1[m-1] == str2[n-1]:
count = longestCommonSubstring(str1, str2, m-1, n-1, count + 1)
else:
count = max(count, max(longestCommonSubstring(str1, str2, m-1, n, 0), longestCommonSubstring(str1, str2, m, n-1, 0)))
return count
Решение для динамического программирования:
def longest_common_substring(str1, str2):
m = len(str1)
n = len(str2)
# Create a 2D matrix to store the lengths of the common substrings
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Variables to keep track of the maximum length and its ending position
max_length = 0
end_position = 0
# Fill in the matrix using a bottom-up approach
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
# If characters match, increment the substring length
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] > max_length:
# Update the maximum length and its ending position
max_length = dp[i][j]
end_position = i
else:
# Characters don't match, reset the substring length
dp[i][j] = 0
# Extract the longest common substring
longest_substring = str1[end_position - max_length:end_position]
# Return the maximum length and the longest common substring
return max_length, longest_substring
# Example usage
str1 = "OldSite:GeeksforGeeks.org"
str2 = "NewSite:GeeksQuiz.com"
length, substring = longest_common_substring(str1, str2)
print("Length of Longest Common Substring:", length)
print("Longest Common Substring:", substring)
Самая длинная возрастающая подпоследовательность:
Самая длинная возрастающая подпоследовательность (LIS) — это понятие в информатике и математике, которое относится к самой длинной подпоследовательности данной последовательности, в которой элементы расположены в строго возрастающем порядке. Проблема LIS заключается в поиске этой самой длинной возрастающей подпоследовательности в заданной последовательности или массиве.
Например, для последовательности [4, 2, 8, 5, 9, 7] возможной самой длинной возрастающей подпоследовательностью будет [2, 5, 7, 9] с длиной 4. Эта подпоследовательность получается путем выбора элементов, которые соблюдать строгий порядок возрастания.
Псевдокод рекурсивного решения с перекрывающимися вызовами и экспоненциальным временем.
lis(arr, n):
if n == 1:
return 1
maxEndingHere = 1
for i in range(1, n):
res = lis(arr, i)
if arr[i-1] < arr[n-1] and res + 1 > maxEndingHere:
maxEndingHere = res + 1
return maxEndingHere
Решение для динамического программирования:
def longest_increasing_subsequence(nums):
n = len(nums)
# Create a list to store the lengths of the increasing subsequences
dp = [1] * n
# Iterate over the elements and fill in the list
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
# If the current element is greater, update the LIS length
dp[i] = max(dp[i], dp[j] + 1)
# Find the maximum LIS length
max_length = max(dp)
# Construct the LIS by tracing back the indices
lis = []
current_length = max_length
for i in range(n - 1, -1, -1):
if dp[i] == current_length:
lis.append(nums[i])
current_length -= 1
# Reverse the LIS to get the correct order
lis.reverse()
# Return the maximum LIS length and the LIS itself
return max_length, lis
# Example usage
sequence = [10, 22, 9, 33, 21, 50, 41, 60]
length, lis = longest_increasing_subsequence(sequence)
print("Length of Longest Increasing Subsequence:", length)
print("Longest Increasing Subsequence:", lis)
Самая длинная палиндромная последовательность:
Самая длинная палиндромная подпоследовательность (LPS) — это понятие в информатике и обработке строк, которое относится к самой длинной подпоследовательности заданной строки, являющейся палиндромом. Палиндром — это последовательность символов, которая одинаково читается вперед и назад.
Например, для строки «BBABCBCAB» возможной самой длинной палиндромной подпоследовательностью будет «BABCBAB», длина которой равна 7. Эта подпоследовательность получается путем выбора символов, образующих палиндром в исходной строке.
Псевдокод рекурсивного решения с перекрывающимися вызовами экспоненциального времени.
longestPalindromicSubsequence(str, start, end):
if start > end:
return 0
if start == end:
return 1
if str[start] == str[end]:
return longestPalindromicSubsequence(str, start+1, end-1) + 2
else:
return max(longestPalindromicSubsequence(str, start+1, end), longestPalindromicSubsequence(str, start, end-1))
Решение для динамического программирования:
def longest_palindromic_subsequence(string):
n = len(string)
# Create a 2D matrix to store the lengths of the palindromic subsequences
dp = [[0] * n for _ in range(n)]
# Initialize the base cases: each character is a palindrome of length 1
for i in range(n):
dp[i][i] = 1
# Fill in the matrix using a bottom-up approach
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if string[i] == string[j]:
# If the characters match, add 2 to the LPS length
dp[i][j] = dp[i + 1][j - 1] + 2
else:
# If the characters don't match, take the maximum of LPS lengths
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
# Return the length of the longest palindromic subsequence
return dp[0][n - 1]
# Example usage
sequence = "character"
length = longest_palindromic_subsequence(sequence)
print("Length of Longest Palindromic Subsequence:", length)
Самая длинная битоническая последовательность:
Самая длинная битоническая подпоследовательность (LBS) — это понятие в информатике и динамическом программировании, которое относится к самой длинной подпоследовательности заданной последовательности, которая сначала увеличивается, а затем уменьшается или остается постоянной.
Например, для последовательности [1, 3, 5, 4, 2, 6, 3] одной из возможных длиннейших битонических подпоследовательностей является [1, 3, 5, 4, 3] с длиной 5. Эта подпоследовательность сначала увеличивает до пика в 5.
Псевдокод рекурсивного решения с перекрывающимися вызовами и экспоненциальным временем.
longestBitonicSubsequence(arr, n):
if n == 0:
return 0
maxLen = 1
for i in range(1, n):
len1 = 0
if arr[i] > arr[i-1]:
len1 = longestBitonicSubsequence(arr, i)
len2 = 0
if arr[i] < arr[n-1]:
len2 = longestBitonicSubsequence(arr, n-i)
maxLen = max(maxLen, len1 + len2 + 1)
return maxLen
Решение для динамического программирования:
def longest_bitonic_subsequence(arr):
n = len(arr)
# Create two arrays to store the longest increasing and decreasing subsequences
lis = [1] * n
lds = [1] * n
# Compute the longest increasing subsequence (LIS) from left to right
for i in range(1, n):
for j in range(i):
if arr[i] > arr[j]:
lis[i] = max(lis[i], lis[j] + 1)
# Compute the longest decreasing subsequence (LDS) from right to left
for i in range(n - 2, -1, -1):
for j in range(n - 1, i, -1):
if arr[i] > arr[j]:
lds[i] = max(lds[i], lds[j] + 1)
# Find the maximum length of the bitonic subsequence
max_length = 0
for i in range(n):
length = lis[i] + lds[i] - 1
max_length = max(max_length, length)
# Return the maximum length of the bitonic subsequence
return max_length
# Example usage
sequence = [1, 11, 2, 10, 4, 5, 2, 1]
length = longest_bitonic_subsequence(sequence)
print("Length of Longest Bitonic Subsequence:", length)
Проблема суммы подмножества:
Задача о сумме подмножеств — известная вычислительная проблема в информатике и математике. Он включает в себя определение того, существует ли подмножество элементов из заданного набора, сумма которых равна заданному целевому значению.
Например, учитывая набор {2, 4, 6, 9} и целевую сумму 13, проблема суммы подмножества спрашивает, существует ли подмножество данного набора, сумма элементов которого равна 13. В этом случае ответ будет да, так как подмножество {4, 9} в сумме дает целевую сумму 13.
Псевдокод рекурсивного решения с перекрывающимися вызовами и экспоненциальным временем.
subsetSum(nums, target, index):
// Base cases
if target == 0:
return true
if index >= length of nums:
return false
// Recursive calls
if nums[index] <= target:
// Include the current number
if subsetSum(nums, target - nums[index], index + 1) is true:
return true
// Exclude the current number
if subsetSum(nums, target, index + 1) is true:
return true
// No subset found
return false
Решение для динамического программирования:
def subset_sum(nums, target):
n = len(nums)
# Create a 2D matrix to store the subset sum possibilities
dp = [[False] * (target + 1) for _ in range(n + 1)]
# Base case: If the target is 0, an empty subset can achieve it
for i in range(n + 1):
dp[i][0] = True
# Fill in the matrix using a bottom-up approach
for i in range(1, n + 1):
for j in range(1, target + 1):
if nums[i - 1] > j:
# If the current number is greater than the target, skip it
dp[i][j] = dp[i - 1][j]
else:
# Consider two possibilities: including or excluding the current number
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
# Return True if a subset with the given target sum exists
return dp[n][target]
# Example usage
numbers = [3, 34, 4, 12, 5, 2]
target_sum = 9
exists = subset_sum(numbers, target_sum)
if exists:
print("Subset with the target sum exists.")
else:
print("Subset with the target sum does not exist.")
Максимальная сумма увеличивающейся подпоследовательности:
Задача о возрастании подпоследовательности с максимальной суммой (MSIS) представляет собой разновидность классической задачи поиска самой длинной возрастающей подпоследовательности. Вместо определения длины самой длинной возрастающей подпоследовательности задача MSIS стремится найти подпоследовательность с максимальной суммой среди всех возрастающих подпоследовательностей в заданной последовательности.
Например, для данной последовательности [4, 6, 1, 3, 8, 4, 9] одной возможной максимальной возрастающей подпоследовательностью является [4, 6, 8, 9] с суммой 27. Эта подпоследовательность представляет возрастающую элементов с максимальной общей суммой в исходной последовательности.
Псевдокод рекурсивного решения с перекрывающимися вызовами и экспоненциальным временем.
maxSumIncreasingSubsequence(arr, n):
if n == 1:
return arr[0]
maxSum = arr[n-1]
for i in range(n-2, -1, -1):
currentSum = maxSumIncreasingSubsequence(arr, i)
if arr[i] < arr[n-1] and currentSum + arr[i] > maxSum:
maxSum = currentSum + arr[i]
return maxSum
Решение для динамического программирования:
def max_sum_increasing_subsequence(nums):
n = len(nums)
# Create a list to store the maximum sum increasing subsequences
dp = nums[:]
# Compute the maximum sum increasing subsequence
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j] and dp[i] < dp[j] + nums[i]:
dp[i] = dp[j] + nums[i]
# Find the maximum sum in the dp list
max_sum = max(dp)
# Return the maximum sum
return max_sum
# Example usage
sequence = [1, 101, 2, 3, 100, 4, 5]
max_sum = max_sum_increasing_subsequence(sequence)
print("Maximum Sum Increasing Subsequence:", max_sum)
Проблема с обменом монет:
Проблема сдачи монет — это классическая алгоритмическая задача, которая включает определение количества способов внести сдачу на заданную сумму денег с использованием определенного набора номиналов монет.
Цель состоит в том, чтобы найти общее количество уникальных способов внести сдачу на целевую сумму, используя заданные монеты.
Например, рассмотрим следующий сценарий:
• Целевая сумма: 5 долларов США.
• Номиналы монет: [1, 2, 5]
В этом случае есть несколько способов внести сдачу на 5 долларов:
• 5 однодолларовых монет
• 2 двухдолларовые монеты и 1 однодолларовая монета
• 1 пятидолларовая монета
Задача о смене монет требует найти все различные комбинации монет, которые в сумме дают целевую сумму.
Псевдокод рекурсивного решения с перекрывающимися рекурсивными вызовами и экспоненциальным временем.
coin_change(coins, amount):
if amount == 0:
return 1
if amount < 0 or len(coins) == 0:
return 0
return coin_change(coins, amount - coins[-1]) + coin_change(coins[:-1], amount)
Решение для динамического программирования:
def coin_change(coins, amount):
# Create a table to store the number of ways to make change for amounts 0 to amount
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
# Example usage:
coins = [1, 2, 5]
target_amount = 5
num_ways = coin_change(coins, target_amount)
print("Number of ways to make change:", num_ways)
Проблема резки стержня:
Задача о перерезании стержня — классическая задача оптимизации в информатике и математике. Проблема состоит в том, чтобы определить лучший способ разрезать стержень заданной длины на более мелкие части, чтобы максимизировать общую стоимость или прибыль.
Псевдокод рекурсивного решения с перекрывающимися вызовами и экспоненциальным временем:
cut_rod(price, n):
if n <= 0:
return 0
max_val = float('-inf')
for i in range(n):
max_val = max(max_val, price[i] + cut_rod(price, n - i - 1))
return max_val
Решение для динамического программирования:
def cut_rod(price, n):
# Create a list to store the optimal values for rod lengths 0 to n
dp = [0] * (n + 1)
for i in range(1, n + 1):
max_val = float('-inf')
for j in range(i):
max_val = max(max_val, price[j] + dp[i - j - 1])
dp[i] = max_val
return dp[n]
# Example usage:
price = [1, 5, 8, 9, 10, 17, 17, 20]
rod_length = 4
max_profit = cut_rod(price, rod_length)
print("Maximum profit for rod length", rod_length, "is:", max_profit)
Задача умножения матриц:
Задача умножения матриц заключается в перемножении двух матриц для получения результирующей матрицы. Для двух матриц A и B, где количество столбцов в матрице A равно количеству строк в матрице B, цель состоит в том, чтобы вычислить матрицу произведения C.
Результирующая матрица C имеет размеры M x N, где M — количество строк в матрице A, а N — количество столбцов в матрице B. Элемент (i, j) матрицы C вычисляется путем скалярного произведения i-я строка матрицы A и j-й столбец матрицы B.
Например, рассмотрим следующие матрицы:
Матрица А:
[ 1. 2. 3 ]
[ 4. 5. 6 ]
Матрица Б:
[ 7. 8 ]
[ 9 10 ]
[11 12 ]
Результирующая матрица C будет:
[ 58. 64 ]
[139 154 ]
Чтобы вычислить каждый элемент результирующей матрицы C, мы берем скалярное произведение соответствующей строки в матрице A и столбца в матрице B. Например, элемент в позиции (1, 1) в C вычисляется как (1 * 7) + (2 * 9) + (3 * 11) = 58.
Псевдокод рекурсивного решения:
matrix_multiplication(A, B):
if dimensions of A and B are compatible for multiplication:
Create a result matrix C with appropriate dimensions
if A and B are 1x1 matrices:
C[0][0] = A[0][0] * B[0][0]
else:
Divide matrices A and B into submatrices
Recursively compute subproducts:
C11 = matrix_multiplication(A11, B11) + matrix_multiplication(A12, B21)
C12 = matrix_multiplication(A11, B12) + matrix_multiplication(A12, B22)
C21 = matrix_multiplication(A21, B11) + matrix_multiplication(A22, B21)
C22 = matrix_multiplication(A21, B12) + matrix_multiplication(A22, B22)
Combine subproducts into result matrix C
return C
else:
Return an error indicating incompatible matrix dimensions
Решение для динамического программирования:
def matrix_chain_multiplication(dimensions):
n = len(dimensions) - 1
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for i in range(1, n - length + 2):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k + 1][j] + dimensions[i - 1] * dimensions[k] * dimensions[j]
if cost < dp[i][j]:
dp[i][j] = cost
return dp[1][n]
