가 m*n 매트릭스있다 "매트릭스에서 오른쪽 하단 왼쪽 상단에서 이동하는 방법의 수"의 재귀 및 동적 솔루션의 복잡성과 우리는 오른쪽 아래 왼쪽 상단에서 모든 가능한 경로를 찾을 필요가있다. 오른쪽 및 아래쪽 방향으로 만 이동할 수 있습니다. 재귀 적 접근 방식에서계산 시간
내가 시간 복잡도가 O 될 것이라고 이해 (2 (m + n)이) :
나는 다음과 같은 의문을 가지고있다. 유도를 사용하여 어떻게 얻을 수 있습니까?
어떻게 동적 프로그래밍 솔루션의 경우 복잡성을 찾을 수 있습니까? 동적 프로그래밍
는 어레이 DP [I] [J]를 작성하려고 DP가 [I]는 [j]가 상단 왼쪽 셀에 도달하는 방법 (Ⅰ, J)의 개수를 의미 세포. 또한 DP [I] [J] DP가 = [I] [J-1] + (DP) [I-1] [J] (코너 케이스를 회피 여기서 I = 1, J = 1). 그래서 전체적으로 n * m 엔트리로 dp 테이블을 채워야하고 각 엔트리는 일정한 엔트리 수 (최대 2에서)에 달려있다. (최대 2시) dp [i-1] [j]과 dp [i] [j -1]. 따라서 복잡도 O (N에서의 m *)이다 O (2 * N *에서의 m) 일 것이다. 우리는 DP 또는 메모이 제이션을 해달라고 (를 구을 수 있습니다) 재귀 그것을 할 경우 수를 찾는 동안
둘째, 당신은 기본적으로 모든 가능한 경로를 추적하고 있습니다. 따라서 복잡도는 왼쪽 상단 셀에서 오른쪽 하단까지의 경로 수입니다. 모든 경로 m-1 수평 N-1 수직 moves.So 경로의 수가된다 것이다 (m + N-2)!/((m-1)! * (n-1)!). 당신이 제안한 것처럼 지수 적이 아닌 복잡성이 있습니다.