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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
#!/usr/bin/env lua
--[[
Challenge 100
TASK #2 > Triangle Sum
Submitted by: Mohammad S Anwar
You are given triangle array.
Write a script to find the minimum path sum from top to bottom.
When you are on index i on the current row then you may move to either
index i or index i + 1 on the next row.
Example 1:
Input: Triangle = [ [1], [2,4], [6,4,9], [5,1,7,2] ]
Output: 8
Explanation: The given triangle
1
2 4
6 4 9
5 1 7 2
The minimum path sum from top to bottom: 1 + 2 + 4 + 1 = 8
[1]
[2] 4
6 [4] 9
5 [1] 7 2
Example 2:
Input: Triangle = [ [3], [3,1], [5,2,3], [4,3,1,3] ]
Output: 7
Explanation: The given triangle
3
3 1
5 2 3
4 3 1 3
The minimum path sum from top to bottom: 3 + 1 + 2 + 1 = 7
[3]
3 [1]
5 [2] 3
4 3 [1] 3
--]]
triangle = {}
function add_row(row, text)
rows = row
table.insert(triangle, {})
for i=1, row do
local s, e = string.find(text, "(%d+)")
local n = tonumber(string.sub(text, s, e))
text = string.sub(text, e+1, -1)
table.insert(triangle[row], n)
end
end
function min_sum(sum, row, col)
sum = sum or 0
row = row or 1
col = col or 1
sum = sum + triangle[row][col]
if row == rows then
return sum
else
local sum1 = min_sum(sum, row+1, col)
local sum2 = min_sum(sum, row+1, col+1)
return math.min(sum1, sum2)
end
end
for i=1, #arg do
add_row(i, arg[i])
end
io.write(min_sum(), "\n")
|
