Letcode: 동적 계획 학습

최근 리코더에서 DP 문제를 풀다가 부딪힌 느낌을 기록해 내가 배운 것을 적는 문제.
 
1、Shortest Path Visiting All Nodes(847)
제목 설명:
An undirected, connected graph of N nodes (labeled  0, 1, 2, ..., N-1 ) is given as graph . graph.length = N , and j != i  is in the list  graph[i]  exactly once, if and only if nodes i and j are connected.
Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.
예제:
Input: [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]
참고:

1 <= graph.length <= 12

0 <= graph[i].length

======================================================================================
제목: 무방향 연결도에서 모든 점을 통과하려면 최소한 몇 개의 변을 거쳐야 하며, 어떤 변, 어떤 점을 반복해서 통과할 수 있다.
사고방식: 제목의 뜻에서 알 수 있듯이 우리는 임의의 노드를 기점으로 한 걸음 수가 가장 적은 길을 찾으면 된다(다음은 모두 걸음수로 답을 묘사한다).그러면 우리는 각 노드를 기점으로 그에 대응하는 최소 걸음수를 찾고 서로 다른 답안에 대해 최소치를 취해 최종 답안을 얻을 수 있다.
어떻게 효율을 높입니까?
큰 문제를 작은 문제로 간주한다. 만약에 N-1개의 점이 있다면 우리는 K를 기점으로 모든 N-1개의 점을 통과하는 최소 걸음수(D로 설정)를 찾았다. 지금 그림에 점을 하나 더하면 K와 연결된다. 그러면 현재 이 점을 기점으로 모든 N개의 점을 통과하는 최소 걸음수는 D+1이다.(1은 점에서 K까지를 나타냅니다).
이제 우리는 우리의 처음 사상을 결합시키고 큰 문제를 작은 문제로 축소하는 사고방식을 더해서 다시 문제를 푸는 사고방식을 정리한다.
1. 우리는 서로 다른 노드를 기점으로 하는 경로를 시도해야 한다.
2. 어떤 변의 어떤 점을 반복해서 지나갈 수 있기 때문에 현재 어떤 점을 지나갔는지 기록하고 모든 점을 지나가면 하나의 경로를 찾을 수 있다.
3. BFS를 사용하여 최소 걸음수를 얻을 수 있다. 왜냐하면 BFS를 사용하는 것은 층별로 확산하는 것과 같기 때문에 우리는 매번 사방으로 한 걸음씩 걸어서 갈 길이 있는지, 길이 있으면 노드가 있는지를 볼 수 있다.
4. BFS를 사용하려면 대기열을 이용하여 하는 것이 가장 편리하다.2, 3 두 점에 따라 원소가 중복 입대할 수 있고 매번 현재 노드와 연결된 노드가 걸음수를 계산한 후에 입대할 수 있다.일단 모든 노드가 방문되면 답을 얻을 수 있다.
5. 4에 따라'동시에'서로 다른 기점의 경로를 계산하면 첫 번째 답이 최종 답이다.[동시에 1을 기점으로 하는 경로가 한 번 확산되면 2를 기점으로 하는 경로가 확산되고 3, 4에서 이렇게 아래로 내려가면 매번 다른 기점의 경로가 한 번 확산된다. 그러면 가장 먼저 모든 점을 통과하는 경로가 가장 작은 것이 틀림없다]
리코드의 제목인 노트는 종종 의도가 있다. 때로는 문제를 푸는 사람이 어떤 시간의 복잡도나 공간의 복잡도를 제시할 수도 있고, 어떤 것이 비교적 간결하고 교묘한 방식으로 문제를 풀 수 있는지를 제시하기도 한다.
이 문제에서 그림 노드는 최대 12이다. 그러면 우리는 2진법으로 집합을 나타내는 사상을 이용하여 현재 어떤 노드를 거쳤는지 나타낼 수 있다. 예를 들어 10011은 현재 0, 1, 4번 노드를 거쳤다는 것을 나타낸다.또한 우리는 기점에 따라 경로를 구분하기 때문에 이미 어떤 점을 통과했는지 나타내는 변수와 이 경로의 기점 변수를 동기화해야 한다.하나의 구조체로 이 두 가지를 표시할 수 있다.
지식 비축 완성, 문제 풀 수 있습니다>>>>>>

class Solution {
public:
    struct state{
        //cover:               
        ///head:          
        int cover,head;
        state(int c,int h):cover(c),head(h){}
    };
    int shortestPathLength(vector>& graph) {
        int n=graph.size();
        //dist[set][start]:   start   ，  set            
        int dist[1< q;
        for(int i=0;i

 2、Unique Binary Search Trees(96)
제목 설명:
Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
====================================================================================
제목이 분명하다. 숫자 N에 모두 N개의 서로 다른 노드가 있음을 표시하고 이 N개의 서로 다른 노드가 몇 개의 두 갈래 검색 트리를 구성할 수 있는지 물어본다.
아이디어:
1. BST의 성질을 이해한다. 각 노드의 왼쪽 트리는 이 노드보다 작고 오른쪽 트리는 이 노드보다 크다.
2. 모두 N개의 노드가 있고 각 노드는 뿌리가 될 수 있으며 서로 다른 노드가 뿌리로 형성된 BST의 수량을 합치면 답이다.
3. 첫 번째 부분에서 우리는 자수의 개념을 언급했다. 자수도 하나의 BST이다. 이것은 우리가 매번 진정으로 BST를 구성할 필요가 없고 몇 가지 가능성만 알면 된다는 것을 암시한다.즉, 어떤 노드를 뿌리로 하는 BST의 경우 왼쪽 나무는 L종이 가능하고 오른쪽 나무는 R종이 가능하면 이 노드를 뿌리로 하는 BST는 L*R종이 가능하다.
4. 제3점에 따라 DP[n]가 1,2로 표시된다고 가정하면...,n개의 노드가 모두 몇 개의 두 갈래 검색 나무를 구성할 수 있습니까?가령 F(i,n)는 i를 루트로 하고 노드가 [1,n]인 정수 서열의 BST의 개수를 나타낸다. 그 중에서 1<=i<=n.DP[n]=F(1,n)+F(2,n)+...+F(n,n).
5. 제3점과 제4점을 결합하면 F(i,n)=[1,i-1] 서열로 구성된 BST의 수량*[i+1,n] 서열로 구성된 BST의 수량을 알 수 있다. 그 중에서 [1,i-1] 서열로 구성된 BST의 수량은 DP[i-1]로 표시할 수 있고 [i+1,n] 서열로 구성된 BST의 수량은 [1,n-(i+1)+1] 즉 [1,n-i] 서열로 구성된 BST의 수량과 같다.그럼 됐어, F(i,n)=DP[i-1]*DP[n-i].
6, 결합 DP[n]=F(1,n)+F(2,n)+...+F(n, n) 및 F(i, n) = DP[i-1] *DP[n-i], DP[n] = DP[0] *DP[n-1] + DP[1] *DP[n-2] +...+DP[n-1]*DP[0]
자, 우리는 우리의 상태 방정식을 얻었다.

class Solution {
public:
    int numTrees(int n) {
        vector dp(n+1,0);
        //  dp                        
        dp[0]=dp[1]=1;
        for(int i=2;i<=n;++i)
            for(int j=0;j<=i-1;++j)
                dp[i]+=dp[j]*dp[i-1-j];
        return dp[n];
    }
};

 
3、Unique Binary Search Trees II(95)
제목 설명:
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
예제:
Input: 3
Output: [   [1,null,3,2],   [3,2,null,1],   [3,1,null,null,2],   [2,1,3],   [1,null,2,null,3] ]
===========================================================================================
이것은 이전 문제의 진급판입니다. 이전 문제는 우리가 BST의 수량을 계산하기만 하면 이 문제는 우리가 가능한 모든 BST를 제시해야 합니다.
아이디어:
아무리 변해도 그 근본을 벗어나지 않는다. 우리의 핵심 사상은 여전히 같은 문제이기 때문에 나는 코드에서 직접 설명한다.주의해야 할 것은 우리의 답은 모든 가능한 BST의 루트 노드를vector에 저장한 다음에 되돌아오는 것이다. (루트 노드를 알면 BFS나 DFS를 통해 전체 나무의 모양을 알 수 있기 때문이다.)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector generateTrees(int n) {
        if(!n)
            return {};
        return solve(1,n);
    }
    //         
    //     ，                       ，              
    //BST [start,end]         
    //   solve       [start,end]     BST
    vector solve(int start,int end)
    {
        vector ans;
        //           ,                      
        if(start>end)
        {
            ans.push_back(NULL);
            return ans;
        }
        //            
        for(int i=start;i<=end;++i)
        {
            //  BST   ，               
            vector left=solve(start,i-1);
            vector right=solve(i+1,end);
            //              BST
            for(int l=0;lleft=left[l];
                    root->right=right[r];
                    ans.push_back(root);
                }
        }
        return ans;
    }
};

 
4、Maximum Subarray(53)
제목 설명:
Given an integer array nums , find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
예제:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
=========================================================================================
제목:
정수와 음수를 포함하는 정수 서열을 한 그룹에 주십시오. 가장 큰 합을 가진 연속 서열을 요구합니다. 가장 큰 합을 요구합니다.
이 문제는 빈거법을 사용하면 틀림없이 답을 찾을 수 있으나, 출제자는 우리가 O(n)의 시간 복잡도를 이용하여 이 문제를 풀기를 바란다.우리도 모든 문제에 대해 효율적인 해법을 배워야만 무엇을 배울 수 있다.
아이디어:
1. 서열에 있는 모든 원소에 대해 우리는 두 가지 방안만 선택하고 선택하지 않으며 우리가 선택한 원소로 구성된 서열이 연속적(인접적)이라는 것을 보장해야 한다.
2. 하나의 원소가 선택된 후에 선택한 연속 서열에 기여할 수 있어야만 선택할 수 있다. 그렇지 않으면 원소와 선택한 연속 서열의 총계가 어느 정도인지 비교하여 답을 업데이트하고 새로운 연속 서열의 선택을 시작해야 한다.
3. 상기 두 가지 점에 따라 dp[i]가 i번째 원소로 끝나고 i번째 원소를 포함하는 최대 연속 서열을 나타낸다고 가정하면 각 dp[i]에 대해 우리는 새로운 연속 서열을 열어야 하는지 아니면 i번째 원소와 이전의 연속 서열을 함께 계산해야 하는지 판단하고 현재 우리가 계산한 최대 연속 서열의 총계를 업데이트해야 한다.

class Solution {
public:
    int maxSubArray(vector& nums) {
        int n=nums.size();
        int dp[n]={0},ans=nums[0];//dp[i]: i     i        
        //DP      
        dp[0]=nums[0];
        for(int i=1;i

 
5、Word Break(139)
제목 설명:
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
참고:

The same word in the dictionary may be reused multiple times in the segmentation.

You may assume the dictionary does not contain duplicate words.

예제:
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code" .
============================================================================================
제목:
문자열과 다른 단어를 포함하는 사전을 드리겠습니다. 문자열이 사전의 단어로 구성될 수 있는지 물어보십시오.할 수 있는지 없는지를 판단했으면 좋겠다.
아이디어:
1. 문자열에 사전에 있는 단어가 있는지 판단하려면 문자열을 분할해야 한다.
2. 빈거하는 방식도 번거롭다. 왜냐하면 모든 문자열이 사전의 단어로 구성되어 있는지 아닌지를 판단하기 때문이다.전체 문자열을 판단하려면 문자열의 뒷부분이 사전의 단어로 구성되어 앞부분과 그렇지 않거나 거꾸로 되어 있으면 안 된다. 즉, 전체 판단 과정은 사실 서로 연결되어 있고 앞부분의 문자열만 사전의 단어로 구성되어 있어야만 우리는 계속 아래로 판단할 수 있다.
3. 두 번째 점에서 dp[i]는 판단할 문자열의 i번째 문자로 끝나는 하위 문자열이 제목 조건을 충족시키는지 가정할 수 있다. 만약에 문자열의 길이가 N이면 dp[0], dp[1],......dp[N-1] 중 하나가 진실이어야 dp[N]가 진실이 있을 수 있다.즉 dp[i]가 진실이라면 i번째 요소로 끝나는 하위 문자열이 사전의 단어로 구성되어 있음을 설명하고, 문자열의 i+1 문자에서 마지막 문자로 구성된 하위 문자열이 사전의 단어라면 전체 문자열이 사전의 단어로 구성될 수 있음을 설명할 수 있다.

class Solution {
public:
     bool wordBreak(string s, vector& wordDict) {
        //     s            ,    unordered_set    
        unordered_set wordset(wordDict.begin(),wordDict.end());
        vector dp(s.size()+1,false);
        //dp      
        dp[0]=true;
        //                 
        for(int i=1;i<=s.size();++i)
            for(int j=i-1;j>=0;--j)
                if(dp[j]==true)
                {
                    if(wordset.count(s.substr(j,i-j))!=0)
                    {
                        dp[i]=true;
                        break;
                    }
                }
         return dp[s.size()];
    }
    
};

 
그리고 문제를 푸는 과정에서 저는 동태적으로 기획된 문제들이 순수한 수학 사상으로 문제를 풀 수 있다는 것을 발견했습니다. 이렇게 하면 때때로 해법이 간편해지고 문제 중의 수학 규칙을 발견할 수 있습니다.
나는 동적 기획 방정식의 선택은 훈련과 상상이 필요한 과정이라고 생각한다. 접촉하자마자 이해할 수 없으니 계속 문제를 풀고 계속 공부해라.