동적 계획 -----매트릭스 최소 경로 및
매트릭스 맵과 그 줄 n, 열 m 을 지정하려면 최소 경로와 줄 수를 되돌려 주십시오.보증 행렬 수는 모두 100보다 작다.
아이디어:
n*m의 행렬 dp를 만듭니다. 그 중에서 dp[i][j]는 위치(0,0)에서 (i,j)에 이르는 최소 경로를 나타냅니다. dp의 첫 번째 줄인 dp[0][j]의 값은 (0,0)에서 계속 오른쪽으로만 도달할 수 있습니다. 이 줄의 값 맵[0][j]의 누적입니다.dp의 첫 번째 열인 dp[i][0]의 값은 (0,0)에서 끊임없이 아래로 내려갈 수 있으며 이 줄의 값인 맵[i][0]를 누적할 수 있다.다른 위치의 값 dp[i][j]에 대해서는 [i-1][j]만 아래로 내려가거나 dp[i][j-1]이 오른쪽으로 한 걸음 내려가기 때문에 dp[i][j]=map[i][j]+min(dp[i-1][j], dp[i][j][j]], [j][j]].
매 dp의 값을 계산하고 마지막 dp[n-1][m-1]의 값은 구한 값이다
int min(int a, int b)
{
if (a < b)
return a;
else
return b;
}
int getMin(vector > map, int n, int m)
{
vector > dp;
dp.resize(n);// dp
for (int i = 0; i < n; i++)
{
dp[i].resize(m);
}
dp[0][0] = map[0][0];
for (int i = 1; i < m; i++)
dp[0][i] = dp[0][i - 1] + map[0][i];
for (int i = 1; i < n; i++)
dp[i][0] = dp[i-1][0] + map[i][0];
for (int i = 1; i < n; i++)
{
for (int j = 1; j < m; j++)
{
dp[i][j] = map[i][j] + min(dp[i - 1][j],dp[i][j - 1]);// ， [i-1][j] ， [i][j-1] ，
}
}
return dp[n - 1][m - 1];
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
