동적 계획 연습 이동 경로
1336 단어 ACM - 동적 계획
샤오밍은 장난꾸러기 아이였는데 어느 날 개미 한 마리를 잡았는데 조심하지 않아 개미의 오른발을 다쳐서 개미는 위로 이동하거나 오른쪽으로 이동할 수밖에 없었다.샤오밍은 이 개미를 왼쪽 아래 네모난 칸에 놓았는데 개미는
왼쪽 아래 칸에서 오른쪽 위 칸으로 이동하고 한 걸음에 한 칸씩 이동한다.개미는 항상 격자 행렬 안에서 움직인다. 서로 다른 이동 노선의 수를 계산해 보세요.
1행 1열의 격자 행렬에 대해 개미는 제자리에서 이동하고 이동 노선 수는 1이다.1행 2열(또는 2행 1열)의 격자 행렬에 대해 개미는 한 번에 오른쪽(또는 위쪽)으로 이동하고 이동 노선 수도 1...2행 3열의 격자 행렬에 대해 아래 그림과 같다.
-------------------
|(2,1)|(2,2)|(2,3)|
-------------------
|(1,1)|(1,2)|(1,3)|
-------------------
개미는 모두 3가지 이동 노선이 있다.
노선1:(1,1)→(1,2)→(1,3)→(2,3)
노선2:(1,1)→(1,2)→(2,2)→(2,3)
노선3:(1,1)→(2,1)→(2,2)→(2,3)
두 개의 정수 m과 n(02 3 샘플 출력)을 포함하는 한 줄만 입력
3
사고방식: 이 한눈에 과거를 떠올리면 (1,1)에서 (m,n)까지의 노선의 개수, (1,1)의 방향은 오른쪽, 그리고 위로 갈 수 있다. 노선의 합은 (1,2)+(2,1)와 같다. 순서대로 내려가면 x===m, y=n까지 이 경계에 도달한 후에 1로 돌아간다. 이것은 하나의 노선이다.
코드:
#if 1
#include
using namespace std;
int m , n ;
int ok(int i ,int j)
{
return ( i == m || j == n ) ;
}
int fun(int x, int y)
{
if(ok(x,y))
return 1;
else
return fun(x+1,y) +fun (x,y+1) ;
}
int main()
{
int a[25][25] ;
cin >> m >> n ;
cout << fun(1,1) < 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
동적 계획 연습 이동 경로묘사×책상 위에 m행 n열의 격자 행렬이 있는데 각 칸을 좌표로 표시한다. 줄 좌표는 아래에서 위로 차례로 증가하고 열 좌표는 왼쪽에서 오른쪽으로 차례로 증가하며 왼쪽 아래 칸의 좌표는 (1,1)이고 오른쪽 위 칸의...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
