[일 일 1 문제] 47. 연말 상여금 (동적 기획, 지역 dp)
9911 단어 매일 한 문제
링크: 연말 보너스 출처: 우 객 망
2. 제목 설명
샤 오 둥 이 있 는 회 사 는 연말 상여금 을 주 려 고 하 는데 샤 오 둥 은 마침 최고 복 지 를 받 았 다. 그 는 회사 연례 회의 에서 추첨 게임 에 참여 하려 고 한다. 게임 은 6 * 6 의 바둑판 에서 진행 되 고 그 위 에 36 개의 가치 가 다른 선물 이 놓 여 있다. 작은 바둑판 위 에 선물 이 하나 놓 여 있다. 그 는 왼쪽 상단 에서 게임 을 시작 해 야 한다. 매번 아래로 또는 오른쪽으로 한 걸음 만 이동 할 수 있다.오른쪽 아래 에 도착 하면 멈 추고 가 는 길에 있 는 격자 안의 선물 을 작은 동쪽 에서 도 받 을 수 있 습 니 다. 작은 동쪽 이 가장 가치 있 는 선물 을 받 을 수 있 도록 알고리즘 을 설계 하 세 요.
6 * 6 의 행렬 board 를 지정 합 니 다. 그 중에서 모든 요 소 는 해당 칸 의 선물 가치 이 고 왼쪽 상단 은 [0, 0] 입 니 다. 얻 을 수 있 는 최대 가 치 를 되 돌려 주 십시오. 모든 선물 가치 가 100 보다 적 고 1000 보다 적 음 을 보증 합 니 다.
3. 문제 해석
이 문 제 는 동적 기획 을 사용 하여 해답 을 구 해 야 한다.정의 f (i, j) 는 왼쪽 상단 에서 좌표 (i, j) 로 가면 얻 을 수 있 는 최대 보상 을 표시 합 니 다.왼쪽 상단 에서 오른쪽 하단 으로 가 는 모든 경 로 를 검색 하여 가장 좋 은 경 로 를 찾 습 니 다.f (i, j) 는 세 가지 상황 으로 나 뉜 다.
첫 번 째 열: f (i, 0) = f (i - 1, 0) + board (i, 0) 첫 번 째 줄: f (0, j) = f (0, j - 1) + b (0, j) 다른 위치: f (i, j) = max {f (i - 1, j), f (i, j - 1)} + board (i, j)
마지막 으로 오른쪽 아래 의 값 을 되 돌려 줍 니 다.
4. 코드 전시
class Bonus {
public:
int getMost(vector<vector<int> > board) {
// write code here
int length = board.size();
int wideth = board[0].size();
vector<vector<int>> allPrice;
for (int i = 0; i < length; ++i) {
vector<int> tmp(wideth, 0);
allPrice.push_back(tmp);
}
allPrice[0][0] = board[0][0];
for (int i = 0; i < length; ++i) {
for (int j = 0; j < wideth; ++j) {
// ，
if (i == 0 && j == 0)
continue;
// ， ， ，
else if (i == 0)
allPrice[i][j] = allPrice[i][j - 1] + board[i][j];
// ， ， ，
else if (j == 0)
allPrice[i][j] = allPrice[i - 1][j] + board[i][j];
else
// 、 ， ，
allPrice[i][j] = max(allPrice[i][j - 1], allPrice[i - 1][j]) + board[i][j];
}
}
// ， ，
return allPrice[length - 1][wideth - 1];
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무는 층순으로 인쇄한다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
