Apes Together Strong.

https://leetcode.com/problems/house-robber-ii/description/ 주어진 정수 배열을 각 집과 그 집에서 rob 할수 있는 value라고 한다. 이때 도둑은 인접해 있는 집은 털수가 없다. 또한 집들이 원형으로 연결되어 있다고 가정한다.따라서 마지막 집과 첫 집은 연결되어 있다.  도둑이 훔칠 수 있는 최대값을 찾아라. House Robber I 문제의 변형이다.  특정 위치에서 idx+2 혹은 idx+3에 접근 할 수 있다. 다만, 0에서 시작했으면 size()-1 까지만 접근 가능하다. 따라서 캐시 버퍼를 만들때 이 경우를 고려한다. 따라서 size() x 2의 캐시 사이즈가 필요하다. 또한 시작 시, 첫 집에서 시작 할 수 있고, 이때는 마지막 집은 접근 할 ..

https://leetcode.com/problems/house-robber/description/ 정수 배열이 주어지고 이것은 각 집과 훔칠 수 있는 돈을 의미한다.도둑은 인접한 집은 방문할 수 없다. 모든 집을 털었을 때, 기대할 수 있는 최대 값을 찾아라. 아래 문제에 비유적 설명을 덧댄 문제.https://leetcode.com/problems/min-cost-climbing-stairs/description/ 인접해서 방문 할 수 없으므로, 특정 위치에서 기대 할수 있는 최대 값은nums[idx] + max(idx+1 이동, idx+2 이동)일 것이다.  코드 더보기 int minCostDP(vector& vCache, int idx, vector& cost){ if(idx >= cost...

https://leetcode.com/problems/min-cost-climbing-stairs/description/ 정수배열 cost는 각 계단을 밟는 비용을 의미한다. 한번에 계단은 하나 혹은 두개씩 밟을 수 있다.시작은 0이나 1 위치에서 시작 할 수 있다.이때, 최고 높은 계단에 도달하기 위한 최소 비용을 구하라.   특정 위치에서 비용은 cost[idx] + min(1단계, 2단계) 일 것이다.  위를 기준으로 코드를 만든다. 코드 더보기int minCostDP(vector& vCache, int idx, vector& cost){ if(idx >= cost.size()) return 0; if(vCache[idx] >= 0) return vCache[id..

https://leetcode.com/problems/climbing-stairs/description/ 한번에 1개 혹은 2개의 계단을 밟을 수 있다고 할 때, 계단을 다 오를 모든 경우의 수를 찾아라. 리마인드 하듯이 문제를 풀어 본다.  DP 문제는 복합적인 듯한 문제를 단일 단계로 해석하는 것이 중요하다.  한 단계에서 1개 혹은 2개만 올라 갈 수 있다. 또한 끝까지 오르면 그만 둔다. 따라서 특정 단계에서 오른 횟수를 구한다면, 그 값을 재활용 할 수 있다.(마지막 계단 바로 앞에서는 1회 두 번, 2회 한번의 두 가지 경우가 존재하고, 이것은 이 전에 무엇을 했던 동일하다.) 코드 더보기int climb(vector& vCache, int idx, int n){ if(idx >= n) ..