-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.rb
More file actions
37 lines (22 loc) · 700 Bytes
/
Solution.rb
File metadata and controls
37 lines (22 loc) · 700 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# @param {Integer[]} nums
# @return {Integer}
def max_coins(nums)
if nums.nil? or nums.size < 1
return 0
end
nums.unshift(1); nums << 1
nums_size = nums.size
dp_matrix = Array.new nums_size
0.upto(nums_size - 1) {|idx| dp_matrix[idx] = Array.new nums_size, 0}
2.upto(nums_size - 1){|k|
0.upto(nums_size - k - 1) {|left|
right = left + k
(left + 1).upto(right - 1){|i|
dp_left = dp_matrix[left][right]; dp_right = nums[left] * nums[i] * nums[right] + dp_matrix[left][i] + dp_matrix[i][right]
dp_matrix[left][right] = dp_left > dp_right ? dp_left : dp_right
}
}
}
dp_matrix[0][nums_size - 1]
end
puts max_coins [3, 1, 5, 8]