LeetCode_91, 120 문항(동적 기획)

LeetCode_91. 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.
해석: 문자열에 몇 가지 다른 알파벳 조합이 있는지 판단하는 전형적인 동적 기획 문제입니다.첫 번째 요소를 고려하면 다음과 같은 몇 가지 상황이 있다. 1. s[i]는 0이고 s[i-1]은 1과 2이다. 분명히 마지막 두 개는 s[i]와 s[i-1]만 조합할 수 있는 요소이기 때문에 두 번째 요소의 종류인 a[i]=a[i-2](물론 s[i-1]가 1과 2가 아니면 어떠한 조합도 될 가능성이 없다. 왜냐하면 30, 40은 자모를 구성하지 않고 단독 0도 자모를 구성할 수 없기 때문이다.2. s[i]가 0이 아니라 s[i-1]이 1이거나 s[i]가 1~6이고 s[i-1]이 2이면 마지막 두 원소를 한 자모로 조합할 수도 있고 두 자모로 나눌 수도 있다. 이때 a[i]=a[i-1]+a[i-2]3, 남은 유별 1, 2를 제외한 이 경우 마지막 원소를 단독으로 한 원소로 만들 수 있다. 이때 a[i]=a[i-1] 상황을 나눈 후 초기 값에 대한 분석과 값을 주의하면 된다.
구체적인 코드는 다음과 같습니다.

class Solution {
public:
    int numDecodings(string s) {
        if(s.empty())return 0;
        int size = s.size();
        int a[10000];
        if(s[0] == '0')return 0;
        if(size == 1){
            return 1;
        }
        a[0] = 1;
        if((s[0] == '1' && s[1] >= '1' && s[1] <= '9') || (s[0] == '2' && s[1] >= '1' && s[1] <= '6'))a[1] = 2;
        else if(s[1] == '0' && (s[0] >= '3' && s[0] <= '9'))return 0;
        else a[1] = 1;
        for(int i = 2; i < size; i++){
            if(s[i] == '0'){
                if(s[i - 1] == '1' || s[i - 1] == '2')a[i] = a[i - 2];
                else return 0;
            }
            else if(s[i - 1] == '1' || (s[i - 1] == '2' && s[i] >= '1' && s[i] <= '6'))a[i] = a[i - 1] + a[i - 2];
            else a[i] = a[i - 1];
        }
        return a[size - 1];
    }
};

LeetCode_120. Triangle 원제: Given a triangle, find the minimum path sum from top to bottom.Each step you may move to adjacent numbers on the row below.
For example, given the following triangle [ —- [2], — [3,4], – [6,5,7], - [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
해석: 맨 위에서 끝까지 가장 작은 합입니다. 줄마다 값이 인접해야 합니다.처음에는 그냥 동적 기획으로 위에서 아래로 순서대로 최소치를 구하면 된다고 생각했지만 맨 밑까지 값이 다르기 때문에 최소치가 바뀔 수 있다는 것을 알게 되었다.그래서 저는 밑에서 끝까지 하는 방법을 바꿨습니다. 아니면 동적 기획으로 각 줄의 i번째 원소를 마지막 원소의 최소와//이때 Minsum은 다음 줄과 인접한 두 원소 부분의 최소와minsum[i]= 이 원소의 값+min(minsum[i],minsum[i+1])
구체적인 코드는 다음과 같습니다.

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {

        if(triangle.size() == 1)return triangle[0][0];
        int size = triangle.size();

        vector<int> minsum(triangle[size - 1]);

        for(int i = size - 2; i >= 0 ; i --){
            for(int j = 0; j < triangle[i].size() ; j ++){
                minsum[j] = triangle[i][j] + min(minsum[j],minsum[j+1]);
            }
        }
        return minsum[0];
    }
};