найти оптимальный путь на 2-й зоне с определенными правилами

Question

У меня есть 2d сетки целых чисел с размерами (n1xn2):

1 4 3 
3 5 7 
2 6 4 

Цель состоит в том, чтобы найти путь слева направо, который имеет самую высокую сумму. Например, в этом случае сумма будет равна 3 + 6 + 7 = 16. Путь может двигаться только на восток и только на соседей самого себя (т. Е. Вы не можете прыгать с 2 на 4, потому что 4 - более чем на расстоянии одной единицы).

Мой вопрос в том, какие методы я могу найти и хранить все возможные пути для пользователя, заданного сетью, зная его размеры? Способно ли хранить всю сетку в 2D-массиве int[rows][cols] или int[cols][rows]? Я предполагаю, что это будет сделано проще всего рекурсивным способом.

Я знаю, что есть похожие вопросы, но я не смог сформулировать для них рабочее решение. Любая помощь будет принята с благодарностью.

Answer 1

Вот попытка, которую я сделал, она работает, но она находится на питоне. Матрица хранится в столбце, основная идея состояла в том, чтобы создать список всех возможных путей по матрице слева направо, а затем в конце найти путь с максимальным значением.

Для каждого элемента возьмите список возможных подпутей и добавьте текущий элемент. Подпункты генерируются рекурсивно.

Я знаю, что это не на Java, но логика одинакова, надеюсь, что это поможет.

matrix = [[1,3,2],[4,5,6],[3,7,4]] 


def findMax(pathList): 
    maxPath = [] 
    maxVal = 0 
    for path in pathList: 
     add = sum(path) 
     if add > maxVal: 
      maxVal = add 
      maxPath = path 
    print "Path: " + str(maxPath) + " val: "+str(maxVal)  

def iterateMatrix(args): #initial method 
    firstcol = args[0] #pop off first column 
    allpaths = [] 
    for i in range(0,len(firstcol)): 
     childPaths = iterateChildren(args,1) #grab all possible subpaths 
     for x in range(0,len(childPaths)): 
      allpaths.append([firstcol[i]]+childPaths[x]) 
    print allpaths 
    #built a list of all possible paths from left to right 
    #now iterate and calculate the sum 
    findMax(allpaths) 

def iterateChildren(args,index):#build up a list of possible combinations of columns in the matrix 
    paths = [] 
    if index == (len(args)-1): #if there are no more possible sub-paths to compute 
     for i in range(0,len(args[index])): 
      paths.append(args[index][i]) 
     return paths 
    else: 
     childPaths = iterateChildren(args, index+1) 
     for x in range(0,len(args[index])): 
      for y in range(0,len(childPaths)): 
       paths.append([args[index][x],childPaths[y]]) 
    return paths 

iterateMatrix(matrix) 

Answer 2

какие методы я могу найти и сохранить все возможные пути на заданном пользователем сетке

Для каждой возможной точки старта (первый вход каждой строки), сделать все возможные шаги вправо и вверх/по/вниз, чтобы остаться на доске. Это может иметь регрессивное решение.

int[rows][cols] или int[cols][rows]

Я обычно использую int[rows][cols], потому что я могу представить его в моем сознании четко - помните, что это означает, что вы должны получить доступ к нему, как grid[y][x], которые могут чувствовать себя странно, чтобы начать с.