선물의 최대 가치(1차원 동적 기획 & 2차원 동적 기획)
m*n의 바둑판의 칸마다 선물이 하나씩 놓여 있고 선물마다 일정한 가치가 있다(가치가 0보다 크다).바둑판의 왼쪽 상단부터 칸에 있는 선물을 들고 오른쪽이나 아래로 한 칸씩 움직여 바둑판의 오른쪽 하단에 도달할 수 있다.바둑판과 그 위에 있는 선물의 가치를 정하면 최대 얼마의 선물을 받을 수 있는지 계산해 보세요.
:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
: 12
: 1→3→5→2→1
해결:
방법1: 동적 기획(2차원).문제풀이의 3대 단계를 요약하고 첫 번째 단계는 확정상태
dp[i][j]를 열거하면 도착i, j위치의 최대 가치를 나타낸다.두 번째 단계, 전태 전이 방정식dp[i][j] = max(dp[i - 1][j], dp[i], [j - 1]) + grid[i][j];.3단계, 첫 번째 행(첫 번째 열)은 왼쪽에서 오른쪽(위에서 아래로)으로만 누적할 수 있는 초기 조건의 경계 조건입니다.방법2: 방법1동태계획(2차원)을 최적화하고 구체적으로 1차원동태계획 방법을 사용하여 해결한다.첫 번째 단계는 확정 상태dp[i][j]를 열거하면 도착i, j 위치의 최대 가치를 나타낸다.두 번째 단계, 전태 전이 방정식dp[i][j] = max(dp[i - 1][j], dp[i], [j - 1]) + grid[i][j];.세 번째 단계, 초기 조건의 경계 조건dp[i][0] = {0}, dp[0][j] = {0}(첫 번째 줄과 첫 번째 열이 모두 0으로 설정됨).답안 참조:
class Solution{
public:
int maxValue(vector<vector<int> > &grid){
// ：
if(grid.empty() || grid[0].empty())
return 0;
vector<vector<int> > dp(grid.size(), vector<int>(grid[0].size(), 0));
dp[0][0] = grid[0][0];
for(int i = 1; i < grid.size(); ++i){
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for(int j = 1; j < grid[0].size(); ++j){
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for(int i = 1; i < grid.size(); ++i){
for(int j = 1; j < grid[0].size(); ++j){
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[grid.size() - 1][grid[0].size() - 1];
// ：
if(grid.empty() || grid[0].empty())
return 0;
vector<int> dp(grid[0].size() + 1, 0);
for(int i = 0; i < grid.size(); ++i){
for(int j = 0; j < grid[0].size(); ++j){
dp[j + 1] = max(dp[j], dp[j + 1]) + grid[i][j];
}
}
return dp[grid[0].size()];
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
