2 차원 배열에서 가장 길게 증가하는 서브 시퀀스 찾기

나는 숙제로이 문제를 가지고 있으며 어디서부터 시작해야할지 전혀 모른다. 재귀 알고리즘 (# 1)을 사용하여 솔루션을 구현했지만 스택을 사용하여 문제를 해결하는 방법을 파악할 수 없습니다. 도움이 필요합니다.2 차원 배열에서 가장 길게 증가하는 서브 시퀀스 찾기

15 x 15 배열에서 가장 길어지는 숫자 시퀀스를 찾습니다. 예를 들어, 어레이 경우, 4 × 4는

97 47 56 36 
35 57 41 13 
89 36 98 75 
25 45 26 17

다음 번호의 긴 증가 시퀀스 길이 17 구성된 여덟, 26, 36, 41, 47, 56, 57의 순서 인 97 참고가 포함 증가하는 순서에는 중복이 없습니다.

이 문제를 해결하고 Java로 구현하는 재귀 알고리즘을 설계하십시오.
스택을 사용하여 동일한 문제를 해결하는 비 반복 알고리즘을 설계하십시오. 이 때문에

출처

2011-03-20 Recursor

표시 한 배열이 4x4 인 모양을 볼 수 없습니다. –

@Recursor "어디서부터 시작해야할지 모르겠습니다." 여기에서 시작하십시오 http://home.earthlink.net/~patricia_shanahan/beginner.html –

죄송합니다, 나는 형식을 엉망으로 만들었어야합니다. - 업데이트 됨. – Recursor

여기에, 숙제 힌트는 다음과 같습니다 당신은 감독 비순환 그래프에 숫자의 배열을 변환 할 수 있습니다. 순차에 허용 된 중복이 없기 때문에 비순환 적입니다. 그 후 알고리즘을 사용하여 가장 긴 경로 문제를 해결하고 그래프에서 최대 길이의 간단한 경로를 찾습니다.

출처

2011-03-20 22:38:34 Chris

감사합니다. 나는 그 효과 (나무)에 대해 뭔가 생각하고 있었지만 좋게 들립니다. 그래프가 array [x, y] -> array [x +/- 1], [y +/- 1]> array [x, y] 등 다른 모든 노드와 같을 것이라고 말할 수 있습니까? 결과를 가져올 때 스택이 어디서 나오는 지 모르겠습니다. – Recursor

@Recursor - 문제를 두 부분으로 처리하십시오. 1) 재귀 알고리즘으로 문제를 해결하십시오. 2) 재귀 적 알고리즘을 반복적 인 알고리즘으로 바꾼다. 재귀 적 버전에서 지역 변수/매개 변수에 보관 된 상태를 유지하기 위해 'Stack'을 사용한다. –

2 차원 배열에서 가장 길게 증가하는 서브 시퀀스 찾기

답변

관련 문제