python - 将多维列表转换为树 Python

Question

我正在尝试编写一些代码，将多维列表转换为字典树。

多维列表可能是这样的

x = [[0,2,5],[1,1,3],[2,1,1]]

列表将始终代表一个 NxN 网格。想象一下。

0 2 5
1 1 3
2 1 1

从左上角开始，您只能从一个节点向右或向下移动以找到它的子节点。

So 0 would have children of 2 and 1
    2 would have children of 5 and 1
        5 would have children of ...
        1 would have children of ...
    1 would have children of 1 and 2
        1 would have children of ...
        2 would have children of ...

所以这棵树会像这样:

                                           0
                                         /    \
                                        /      \
                                       /        \
                                      /          \
                                     /            \
                                    2             1
                                   /\             /\
                                  /  \           /  \
                                 /    \         /    \
                                1      5       2      1
                               /\      |       |      /\
                              /  \     |       |     /  \
                             1   3     3       1    3    1
                             |   |     |       |    |    |
                             1   1     1       1    1    1

这就是节点及其子节点的可视化树的样子，它将由以下结构中的代码表示:

 tree = {'value': 0, 'children': [
            {'value': 2, 'children': [
                {'value': 1, 'children': [
                    {'value': 1, 'children': [
                        {'value': 1, 'children': [None, None]}
                    ]},
                    {'value': 3, 'children': [
                        {'value': 1, 'children': [None, None]}
                    ]}
                ]},
                {'value': 5, 'children': [
                    {'value': 3, 'children': [
                        {'value': 1, 'children': [None, None]}
                    ]}
                ]}
            ]},
            {'value': 1, 'children': [
                {'value': 1, 'children': [
                    {'value': 3, 'children': [
                        {'value': 1, 'children': [None, None]}
                    ]},
                    {'value': 1, 'children': [
                        {'value': 1, 'children': [None, None]}
                    ]}
                ]},
                {'value': 2, 'children': [
                    {'value': 1, 'children': [
                        {'value': 1, 'children': [None, None]}
                    ]}
                ]}
            ]}
        ]}

如果有任何有效的方法可以将上述网格转换为这种形状优美的字典，那么在正确的方向上进行指导将非常有帮助。我试过这个:http://repl.it/6sU没有运气，因为递归太深了，但是我想不出其他方法来做。谢谢。

Answer 1

我将针对您遇到的实际问题发布一个解决方案，正如您在评论中提到的那样，它是找到最接近给定数字的总和，其中候选总和是通过仅移动遍历 NxN 矩阵来找到的向下和向右。

def gridsums(grid, x, y, memo):
    if memo[x][y] is not None:
        return memo[x][y]

    if x == 0 and y == 0:
        sums = [0]
    elif x == 0:
        sums = gridsums(grid, x, y-1, memo)
    elif y == 0:
        sums = gridsums(grid, x-1, y, memo)
    else:
        sums = gridsums(grid, x-1, y, memo) + gridsums(grid, x, y-1, memo)

    sums = [grid[x][y] + s for s in sums]
    memo[x][y] = sums
    return sums

def gridsumsfast(grid):
    memo = []
    for row in grid:
        memo.append([])
        for cell in row:
            memo[-1].append(None)

    return gridsums(grid, len(grid[0]) - 1, len(grid) - 1, memo)

最简单的版本是完全删除“备忘录”的东西，但是实现了“动态规划”以缓存以前计算的结果并避免重复工作。剩下的是一个相当简单的递归解决方案，它直接产生所有可能的总和(包括重复项)。

对于您的示例数据，结果是 [11, 7, 6, 5, 4, 5]。