귀속과 동태 기획

귀착사상

귀속은 운행 과정에서 자신을 호출하는 것이다.구성 귀환에 필요한 조건: 함수 플러그인 호출 프로세스 예시 함수 플러그인 호출 프로세스 예시
4

자문제는 원시문제와 같은 일이고 더욱 간단해야 한다

4

그 자체를 무제한으로 호출할 수 없고 반드시 수출이 있어야 하며 비귀속 상황으로 간소화해야 한다

수학과 컴퓨터 과학에서 귀속은 간단한 기본 상황에 의해 정의된 대상이나 방법을 가리키며 기타 모든 상황을 기본 상황으로 환원시킬 수 있도록 규정한다.
예를 들어 다음은 누군가의 조상에 대한 귀속 정의이다. 누군가의 양친은 그의 조상이다(기본적인 상황).누군가의 조상 양친 역시 누군가의 조상이다.피보나치 수열(Fibonacci Sequence)은 황금분할 수열이라고도 하는데 이런 수열을 가리킨다. 1, 1, 2, 3, 5, 8, 13, 21...
피보나치 수열은 전형적인 귀속 사례이다. 귀속 관계는 실체 자신과 자신이 관계를 맺는 것이다.Fib(0)=1 [기본상황] Fib(1)=1 [기본상황]은 모든 n>1에 대한 정수: Fib(n)=(Fib(n-1)+Fib(n-2)[귀속 정의]는 많은 수학 함수를 귀속 표시할 수 있지만 실제 응용에서는 귀속 정의의 높은 비용이 뒷걸음질치게 된다.예를 들어 곱하기(1)=1[기본상황]는 모든 n>1에 대한 정수: 곱하기(n)=(n*곱하기(n-1))[귀속 정의]는 이해하기 쉬운 심리 모델로 귀속 정의가 대상에 대한 정의는'이전에 정의한'같은 대상에 따라 정의된 것이라고 생각한다.예를 들어 당신은 어떻게 해야만 100개의 상자를 이동할 수 있습니까?답:당신은 먼저 상자를 이동하고 그것이 이동하는 위치를 기록한 다음에 비교적 작은 문제를 해결한다:당신은 어떻게 해야 99개의 상자를 이동할 수 있습니까?결국, 당신의 문제는 상자를 어떻게 이동하는가로 바뀔 것이다. 이때 당신은 어떻게 해야 할지 이미 알고 있다.

DP사상

동적 기획(dynamic programming)은 운기획학의 한 가지로 구해 결정 과정(decision process)에 가장 최적화된 수학 방법이다.1950년대 초 미국 수학자 R.E.Bellman 등은 다단계 의사결정 과정(multistep decision process)의 최적화 문제를 연구할 때 유명한 최적화 원리(principle of optimality)를 제시하여 다단계 과정을 일련의 단일 단계 문제로 전환시키고 각 단계 간의 관계를 이용하여 하나하나 해답을 구하며 이런 과정의 최적화 문제를 해결하는 새로운 방법인 동적 기획을 창립했다.
동적 기획은 일반적으로 선형 게이지, 지역 게이지, 나무 게이지, 배낭 게이지 네 종류로 나눌 수 있다.예를 들어 선형동규: 미사일 차단, 합창대형, 지뢰 파기, 학교 건설, 검객 결투 등;지역동규: 돌합병, 가산점 두 갈래 나무, 단어 개수 통계, 포병포진 등;나무형동규: 탐식하는 구두룡, 2분 찾기 나무, 모임의 즐거움, 숫자 삼각형 등;가방 문제:01 가방 문제, 완전 가방 문제, 그룹 가방 문제, 2차원 가방, 포장 문제, 우유 짜기 등;
예제: 리코드 198
문제 설명

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.
Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

문제 해결 방법 코드:

class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 1: return nums[0]
        dp = [0] * (n+1)
        for i in range(1, n+1):
            if i == 1:
                dp[i] = nums[i-1]
            elif i == 2:
                dp[i] = max(dp[i-1], nums[i-1])
            else:
                dp[i] = max(dp[i-1], nums[i-1] + dp[i-2])
        if n == 2:
            return max(dp[-2], dp[-1])

        return dp[-1]