어떻게 피보나치 수열을 얻었습니까?(m*n 크기의 직사각형, 왼쪽 상단에서 왼쪽 하단까지 몇 가지 주법이 있습니까? 인용 문제와 총결을 포함합니다)
1278 단어 알고리즘 문제
1m*n 크기의 직사각형으로 왼쪽 상단에서 왼쪽 하단까지 몇 가지 주법이 있습니까?
이것은 마이크로소프트의 면접 문제로 오른쪽으로 가거나 아래로 갈 수밖에 없다.
방법 1
이 문제를 보면 어렵지 않다. 가장 직관적인 생각은 깊이 검색이다. 그러나 이것은 좀 번거롭다. 만약에 내가 m와 n이 비교적 크면 깊은 귀속 깊이가 있고 연산이 매우 느리며 중복 연산도 있다.중복 연산을 보면 동적 기획을 할 수 있다.어떻게 그 귀속식을 얻었습니까?만약 왼쪽 상단 좌표가 (0,0)이라면, 나는 지금 (i,j)에 있는데, 어떻게 이 점에 도달할 수 있습니까?(i-1, j)와(i, j-1)에서만 도착(i, j)할 수 있으며, m(i, j)로 도착(i, j)할 수 있는 경로 갯수를 기록하면 m(i, j)=m(i-1, j)+m(i, j-1), 즉 귀속 관계이다.바로 코드를 올려주세요.
int pathNum(int m,int n)
{
m=m+1;
n=n+1;
int **p=new int*[m];
for(int i=0;i방법 2
(0,0,)부터 (m,n)까지 총 x방향은 m보, y방향은 n보를 걸었다.그러고 보니 배열 조합에 문제가 있는 것 같지 않아요? 그럼 간단해요. 결과는 C(m+n)n=(m+n)!/(m!*n!)
인신일: 지금 한 걸음이나 두 걸음을 뛸 수 있을까요?어떻게 풀어요?
사실 방법 1과 비교적 유사한데, 고려하는 상황이 좀 많다
인용2: 일부 경로가 제한되면,
사고방식은 역시 방법에서 출발하지만 판단하고 다음과 같이 분석한다.
만약 현재 (i, j) 에 있다면, (i-1, j) 에서 (i, j) 까지 제한을 받습니까?(i, j-1)부터 (i, j)까지 제한을 받습니까?
제한을 받으면 그 항목을 버리고 다 제한을 받으면 그 점에 도달할 방법이 없다.이것이 바로 제한된 경로를 해결하는 사고방식이다.
요약: 1 제한을 받지 않는 유사한 문제 유형은 계단을 오르는 것(링크를 클릭하면 열기), 한 로봇이 n미터를 가면 1, 2, 3미터를 갈 수 있다. 주로 두 가지 방법이 있다. 1) 귀속 관계를 얻고 2) 배열 조합
2 제한된 경로, 반복 관계를 통해서만 가능하며 제한된 경로를 검사할 때마다
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[못 푼 문제] 백준 10989번sys.stdin.readline()을 사용하여 input의 시간을 줄였다. 또한 입력 가능한 수의 개수가 10,000,000개 이고 최대 입력 가능한 수가 10,000이기 때문에 모든 수를 입력 받아 리스트로 만들...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
