동적 기획 요약 - 1차원 동적 기획 - 시간 복잡도 O(n), 문제 [Leet Code] Jump Game, Decode Ways

인용문
1차원 동적 계획은 전이 방정식에 따라 복잡도는 일반적으로 두 가지 상황이 있다.
func(i)는func(i-1)와만 관련이 있고 시간 복잡도는 O(n)이다. 이런 상황에서 공간 복잡도는 종종 O(1)로 최적화할 수 있다.
func(i)는func(1~i-1)와 관련이 있으며 시간 복잡도는 O(n*n)이다. 이런 상황에서 공간 복잡도는 일반적으로 최적화할 수 없고 여전히 O(n)이다.
이 편에서는 제1종의 상황을 토론한다
 
예제 1
Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:A =  [2,3,1,1,4] , return  true .
A =  [3,2,1,0,4] , return  false .

class Solution {

public:

    bool canJump(int A[], int n) {

    }

};

 
이 문제는 틀림없이 DP로 만든 것이다.
나의 첫 번째 생각은 bool reachable [n] 수조를 정의하는 것이고,reachable [i] =true는 제 i 요소가 끝에 도달할 수 있음을 나타낸다.
따라서 reachable [i] = if(reachable [i+1] = true | reachable [i+2] = true | | | | | reachable [i+A[i]] = = true)
reachable[0]로 돌아갑니다.
그러나 이런 사고방식으로 쓰면 2차원 순환으로 전체 과정을 완성해야 하기 때문에 시간 복잡도는 여전히 O(n2)이다
이런 사고방식으로 쓴 코드:

class Solution {

public:

    bool canJump(int A[], int n) {

        if(n <= 1) return true;

        bool *reachable = new bool[n-1];

        if(A[0] >= (n-1)) return true;

        for(int i = n-2; i >= 0; --i){

            if(A[i] >= (n-1-i)) reachable[i] = true;

            else{

                int j;

                for(j = 1; j <= A[i]; ++j){

                    if(reachable[i+j]){

                        reachable[i] = true;

                        break;

                    }

                }

                if(j > A[i]) reachable[i] = false;

            }

        }

        return reachable[0];

    }

};

LetCode의 빅데이터는 초과할 수 없습니다. 시간을 초과합니다.
 
인터넷에서 참고했어요.http://blog.csdn.net/xiaozhuaixifu/article/details/13628465라는 논문을 통해 상기 사고방식의 상태 이동 방정식이 효율이 낮은 이유는 bool을 수조 요소로 하기 때문이라는 것을 알게 되었다. 이런 사고방식 자체는 동적 기획에서 추천한 사고방식이 아니다.동적 기획은 시간을 절약하기 위해 가능한 한 수조를 이용하여 가장 많은 정보를 저장하고 bool값은true와false만 저장할 수 있다.
개선판의 사고방식은 이 수조는 단순히 이런 bool 값에 도달할 수 있거나 도달할 수 없는 것이 아니라 0위치에서 출발하는 최대 도달 길이에 저장된다는 것이다.그룹 int can Still Walk [n]을 정의하고, can Still Walk [i]는 i 위치에 도달한 후에도 나갈 여력이 있는 최대 길이를 나타낸다.canStillWalk[i] < 0이면 위치 i에 도달할 수 없습니다.
상태 전환 방정식은 다음과 같습니다.
canStillWalk[i] = max(canStillWalk[i-1], A[i-1]) - 1;
이렇게 하면 can Still Walk[i]를 계산할 때 순환이 필요하지 않습니다.
시간 복잡도 O(n), 공간 복잡도 O(n)

class Solution {

public:

    bool canJump(int A[], int n) {

        if(n <= 1) return true;

        if(A[0] >= (n-1)) return true;

        int *canStillWalk = new int[n];

        canStillWalk[0] = A[0];

        for(int i = 1; i < n; ++i){

            canStillWalk[i] = max(canStillWalk[i-1], A[i-1]) - 1;

            if(canStillWalk[i] < 0) return false;

        }

        return canStillWalk[n-1] >= 0;

    }

};

 
이어서 간소화할 수 있다. 왜냐하면 can Still Walk[i]는 can Still Walk[i-1]와만 관련이 있기 때문에 우리는 메시지를 저장할 수 있는 그룹을 정의할 필요가 없다. 바로pre와cur로 해결할 수 있다. 시간 복잡도 O(n), 공간 복잡도 O(1):

class Solution {

public:

    bool canJump(int A[], int n) {

        if(n <= 1) return true;

        if(A[0] >= (n-1)) return true;

        int pre = A[0], cur = 0;

        for(int i = 1; i < n; ++i){

            cur = max(pre, A[i-1]) - 1;

            if(cur < 0) return false;

            pre = cur;

        }

        return cur >= 0;

    }

};

  
소결
동적 기획의 문제에 있어 상태 이동 방정식이 비교적 중요하다. 이 문제의 특수성은'보수연속'에 있다. 즉, A[i]=s는 A[i]에서 1~s보를 갈 수 있다는 것을 나타낸다. 주어진 몇 개의 불연속적인 값이 아니라 A[i]에서 1~s보를 갈 수 있다는 것을 의미한다. 그러면 우리는 가장 긴 거리라는 이동 방정식을 정의함으로써 사상을 간소화할 수 있다.
 
예제 2
Decode Ways
A message containing letters from  A-Z  is being encoded to numbers using the following mapping:

'A' -> 1

'B' -> 2

...

'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.
For example,Given encoded message  "12" , it could be decoded as  "AB"  (1 2) or  "L"  (12).
The number of ways decoding  "12"  is 2.
 
시간 복잡도 O(n), 공간 복잡도 O(1) 해법

class Solution {

public:

    int numDecodings(string s) {

        if(s.empty()) return 0;

        int pre = -1, cur = 1, tmp;

        for(int i = 1; i <= s.length(); ++i){

            tmp = cur;

            if(s[i-1] == '0'){

                if(isCode(s, i-2, i-1)) cur = pre;

                else return 0;

            }else if(isCode(s, i-2, i-1))

                cur += pre;;

            pre = tmp;

        }

        return cur;

    }

private:

    bool isCode(string &s, int i, int j){

        if(i < 0) return false;

        if(s[i] >= '3' || s[i] == '0') return false;

        if(s[i] == '2' && s[j] >= '7') return false;

        return true;

    }

};