前几天被一个动态规划的题目难倒了。。。( a dynamic program question:triangle. )
访问量: 2982
参考：http://poj.org/problem?id=1163
做为一个WEB开发的人，我表示对数据结构一无所知，一塌糊涂，忘的一光二净，看题时一头雾水，解题时异想天开。所以。。。同学们不必看了。。。写在这里，就不往github上放了。。。
有个题目：给出一个树状结构：
A
B C
D E F
G H I J
列出所有可能的路径， 例如：
1. ABDG
2. ABDH
3. ABEH
4. ABEI 。。。
一想就是个递归函数。。。头大啊。所以，我的思维不够灵光，只好用最笨的方法来遍历它。RUBY代码放在这里，有机缘的时候再试试其他的ACM题目吧。。。
class Tree
def initialize(nodes)
@nodes = nodes
# init the matrix
@matrix = []
@nodes.each_with_index { |row, i |
@matrix[i] = []
row.each_with_index { |cell, j|
@matrix[i][j] = cell
}
}
end
def print
@matrix.each { |row| puts row.inspect; }
end
def routes
@result = []
set_route_by_node(0, 0, "")
puts '==='
puts @result
end
def set_route_by_node(column_index, row_index, route_from_parent)
route = route_from_parent + @matrix[row_index][column_index]
puts "== considering: row:#{row_index}, column:#{column_index}, route: #{route}"
# should return for the leaves.
if row_index + 1 == @matrix.size
puts '++++++++++++++++++++++++++++++++== a branch is done'
@result << route
else
# left child
puts '-- setting left child'
set_route_by_node(column_index, row_index + 1, route)
# right child
puts '-- setting right child'
set_route_by_node(column_index + 1, row_index + 1, route)
end
end
end
tree = Tree.new([['a'], ['b','c'], ['d','e','f'], ['g','h','i','j']])
# a
# b c
# d e f
# g h i j
tree.print
# "a,b,d,g"
# "a,b,d,h"
# "a,b,e,g"
# "a,b,e,h" ...
tree.routes
输出是：
sg552@siwei-moto:~/workspace/recursive_function_exams$ ruby print_tree.rb ["a"] ["b", "c"] ["d", "e", "f"] ["g", "h", "i", "j"] == considering: row:0, column:0, route: a -- setting left child == considering: row:1, column:0, route: ab -- setting left child == considering: row:2, column:0, route: abd -- setting left child == considering: row:3, column:0, route: abdg ++++++++++++++++++++++++++++++++== a branch is done -- setting right child == considering: row:3, column:1, route: abdh ++++++++++++++++++++++++++++++++== a branch is done -- setting right child == considering: row:2, column:1, route: abe -- setting left child == considering: row:3, column:1, route: abeh ++++++++++++++++++++++++++++++++== a branch is done -- setting right child == considering: row:3, column:2, route: abei ++++++++++++++++++++++++++++++++== a branch is done -- setting right child == considering: row:1, column:1, route: ac -- setting left child == considering: row:2, column:1, route: ace -- setting left child == considering: row:3, column:1, route: aceh ++++++++++++++++++++++++++++++++== a branch is done -- setting right child == considering: row:3, column:2, route: acei ++++++++++++++++++++++++++++++++== a branch is done -- setting right child == considering: row:2, column:2, route: acf -- setting left child == considering: row:3, column:2, route: acfi ++++++++++++++++++++++++++++++++== a branch is done -- setting right child == considering: row:3, column:3, route: acfj ++++++++++++++++++++++++++++++++== a branch is done === abdg abdh abeh abei aceh acei acfi acfj