leetcode 198번 집 약탈(동적 기획)
각 집의 보관 금액을 대표하는 비음정수조를 정해 경보 장치를 건드리지 않은 상태에서 하룻밤 안에 훔칠 수 있는 최고 금액을 계산한다.예1: 입력: [1,2,3,1] 출력: 4 해석: 1번 집(금액=1)을 훔친 다음에 3번 집(금액=3)을 훔친다.훔친 최고 금액 = 1 + 3 = 4.
예2: 입력: [2,7,9,3,1] 출력: 12 해석: 1번 집을 훔치다(금액=2), 3번 집을 훔치다(금액=9), 이어서 5번 집을 훔친다(금액=1).훔친 최고 금액 = 2 + 9 + 1 = 12.
출처: 리코더 링크:https://leetcode-cn.com/problems/house-robber저작권은 인터넷 소유에 귀속된다.상업 전재는 관공서에 연락하여 권한을 수여하고 비상업 전재는 출처를 밝혀 주십시오.
문제 풀이:
class Solution {
public:
int rob(vector<int>& nums)
{
int n = nums.size();
if(n == 0)
return 0;
if(n == 1)
return nums[0];
vector<int> dp(n+1,0);
dp[1] = nums[0];
for(int i=2;i<=n;++i)
dp[i] = max(dp[i-1],dp[i-2]+nums[i-1]);
return dp[n];
}
};
문제풀이 사고방식: 한 방에 대해 도둑은 두 가지 선택이 있다. 훔치거나 dp[i]=max(dp[i-1], dp[i-2]+nums[i-1]).
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
