몇 가지 알고리즘 사상:

1. 귀속(이전 5일차 작업 유지) LeetCode를 통해 [70. 계단 오르기] 중국어 학습 경로:https://leetcode-cn.com/problems/climbing-stairs/submissions/사고방식1: n=1~4의 결과를 열거한 결과 규칙이 피보나치 수열과 매우 비슷하다는 것을 발견했다. 동적 기획 DP 방식으로 int*sum=new int[n];이전 두 상황의 합을 새 값으로 되돌려줍니다.코드는 다음과 같습니다. class Solution { public: int climbStairs(int n) { if(n==0) return 0; if(n==1) return 1; int* sum=new int[n]; sum[0]=1; sum[1]=2; for(int i=2;i 사고방식2: 귀속 호출 방식으로 자신의 지난 두 번의 계산 결과를 호출하여 되돌려준다.근데 제출이 안돼요. 왜 운행이 초과됐는지 모르겠어요.실행할 때 ok였어요.https://leetcode-cn.com/problems/climbing-stairs/submissions/

둘째, 거슬러 올라가는 문제는 어떤 성질(구속 조건)의 모든 해를 만족시키거나 가장 좋은 해를 요구할 때 거슬러 올라가는 방법을 사용한다.실현 방법은 두 가지가 있는데 그것이 바로 역귀와 역귀(迭代) 역귀 사고방식이다. 검색할 때 깊이 우선 알고리즘 DFS를 사용하고 한 경로가 요구를 충족시키면 끝까지 검색하고 조건에 부합되지 않으면 이 하위 노드의 모든 경로를 버리고 등급이 높은 노드로 돌아가서 다시 검색한다. 부합되지 않으면 역귀이다. 거슬러 올라가는 알고리즘을 이용하여 8황후 문제의 국제 장기 8*8 바둑판을 풀면 황후는 가로 세로 사선을 따라 임의의 걸음수를 걸을 수 있다.황후의 자리를 놓고 다음 황후는 어떤 줄에 있을 때 점위 황후와 같은 세로 사선에 있는지 검색해야 한다. 끝까지 있으면 줄로 돌아가 이동하고 후속 절차를 반복해야 한다.중국어 경로:https://leetcode-cn.com/problems/n-queens/ class Solution { public: vector> solveNQueens(int n) { if( n <= 0) return vector< vector< string> >(); int col[n]; vector< vector< string> > res; queens( col, 0, n, res); return res; } void queens( int * col, int row, int n, vector< vector< string> > &res){ if( row == n){ push(col, res, n); return; } for( int i = 0; i < n; ++i){ col[row] = i; bool flag = true; for( int j = 0; j < row; ++j){ if( col[row] == col[j] || col[row] - col[j] == row - j || col[row] - col[j] == j - row){ flag = false; break; } } if(flag) queens( col, row+1, n, res); } } // 값을 수조에 넣다 void push( int * col, vector< vector< string> > &res, int n){ vector< string> temp;//여기는 초기화할 수 없습니다. 그렇지 않으면 초기화 값이 있을 것입니다. for( int i = 0; i < n; ++i){ string str = ""; for( int j = 0; j < n; ++j){ if( col[i] == j) str += 'Q'; else str += '.'; } temp.push_back(str); } res.push_back(temp); } }; 거슬러 올라가는 알고리즘을 이용하여 0-1 가방 문제를 풀다

3. 분치 분할 알고리즘을 이용하여 한 그룹의 데이터를 구하는 역순은 개수에 대한 역순을 구하고 개수에 대해 분할 알고리즘(Divide and Conquer)을 사용하는 매우 전형적인 응용 프로그램인 통합 정렬(MERGE-SORT)은 통합 작업에 구축된 효과적인 정렬 알고리즘으로 시간 복잡도는 O(nlogn)이다.기존 서열의 하위 서열을 합쳐서 완전히 질서정연한 서열을 얻기;즉, 먼저 각 하위 시퀀스를 질서정연하게 한 다음에 하위 시퀀스 세그먼트 사이를 질서정연하게 합니다.만약 두 개의 질서표를 하나의 질서표로 합치면 이로[귀합]이라고 부른다. 사고방식: 역순 쌍은 한 수조에 있는 두 개의 숫자를 가리킨다. 만약에 앞의 숫자가 뒤의 숫자보다 크면 이 두 숫자는 하나의 역순 쌍을 구성한다.선분 후치: 한 수조를 두 개의 대칭 부분(기수 그룹을 어떻게 하는지 나는 아직 연구하지 않았다)을 분해하고 좌우 수조를 각각 분해하여 하나의 원소를 하나의 수조로 분해한 후에 최신 좌우 수조를 비교하고 정렬하며 역순을 기록하고 하나의 수조로 합친다. 이렇게 반복하여 최종적이고 완전한 서열표가 된다.

4. 동적 기획 0-1 가방 문제 ※ 1, 2, 3, 4, 5의 다섯 가지 아이템이 있습니다. 무게는 각각 2, 2, 6, 5, 4, 그들의 가치는 각각 6, 3, 5, 4, 6입니다. 현재 무게가 10인 가방을 드리겠습니다. 가방에 넣은 물건이 가장 큰 가치를 가지게 하는 방법은 무엇입니까?동적 기획의 핵심 과정은 두 가지가 있는데 하나는 문제를 찾아내는'자 상태'이다. 또 하나는'상태 이동 방정식'(이른바 추이 공식)을 구축하는 것이다. 동적 기획이 문제를 해결하는 핵심은 표를 작성하고 표를 작성하면 가장 좋은 결과를 찾을 수 있다.이를 통해 점차적인 관계식을 얻을 수 있다. Vi는 i번째 물품의 가치를 나타내고, Wi는 i번째 물품의 부피(중량)를 나타낸다. 1) j 2) j>=w(i) V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝ 최소 경로와 (상세히 보면 Minimum Path Sum) 동적 기획의 과정은 귀속의 역과정으로 볼 수 있다. 귀속은 위에서 아래로 구해하는 것이기 때문에 모든 큰 문제는 먼저 서브 문제를 구해야 한다. 따라서 동적 기획은 작은 서브 문제를 먼저 구해내고 순서대로 위로 올라가기 때문에 큰 문제에 필요한 서브 문제는 미리 구해야 한다. 선생은 2차원 dp표를 만들고 역귀의 반대 방향에 따라 해답을 구한다.먼저 dp표의 맨 오른쪽 하단 + 마지막 줄 + 마지막 열의 위치를 기입한다.그리고 일반적인 위치를 찾아 그 아래의 위치와 왼쪽의 위치에 의존하기 때문에 우리는 순서대로 아래에서 위로 오른쪽으로 왼쪽으로 하고 전체 dp표를 작성한다. 마지막으로 dp[0][0]가 답이다.참조:https://blog.csdn.net/zxzxzx0119/article/details/81227300 class Solution { public: int minPathSum(vector>& grid) { int mm=grid.size(); int nn=grid[0].size(); vector > dis; vector vec; vec.push_back(grid[0][0]); for (int i=1;i 프로그래밍 구현 레빈슈타인 최단 편집 거리 word1 몇 단계의 조작을 거쳐 (추가, 삭제, 교체)word2:https://leetcode-cn.com/problems/edit-distance/submissions/ 프로그래밍은 두 문자열의 최장 공통 하위 시퀀스를 찾습니다 프로그래밍은 데이터 시퀀스의 최장 증가 서브시퀀스를 실현한다

그에 맞는 Leet Code 연습 문제. 실전 귀속: Leetcode의 Letter Combinations of a Phone Number(17) 및permutations(46) 완성 (지난 6일차 작업 유지) 실전 DP: 완성 0-1 가방 문제 실현(자기 실현) 및 Leetcode Palindrome Partitioning II(132) 제목: leetcode198 House Robber (지난 7일차 작업 유지) Regular Expression Matching(정규 표현식 일치) 영문:https://leetcode.com/problems/regular-expression-matching/ public: bool isMatch(string s, string p) { int m = s.size(), n = p.size(); vector> dp(m + 1, vector(n + 1, false)); dp[0][0] = true; for (int i = 1; i <= n; ++i) { if (p[i - 1] == '.') dp[0][i] = dp[0][i - 1]; } for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (p[j - 1] == '.') { dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; } else { dp[i][j] = (s[i - 1] == p[j - 1] || p[j - 1] == '*') && dp[i - 1][j - 1]; } } } return dp[m][n]; } }; 중국어 버전:https://leetcode-cn.com/problems/regular-expression-matching/ Minimum Path Sum(최소 경로 및) 영문:https://leetcode.com/problems/minimum-path-sum/ 중국어 버전:https://leetcode-cn.com/problems/minimum-path-sum/ ↑ 4 동적 기획 2https://leetcode-cn.com/problems/minimum-path-sum/ Coin Change(잔돈 교환) 영문:https://leetcode.com/problems/coin-change/ 중국어 버전:https://leetcode-cn.com/problems/coin-change/반복 + memo의 DP class Solution { public: int coinChange(vector& coins, int amount) { vector memo(amount + 1, INT_MAX); memo[0] = 0; return coinChangeDFS(coins, amount, memo); } int coinChangeDFS(vector& coins, int target, vector& memo) { if (target < 0) return - 1; if (memo[target] != INT_MAX) return memo[target]; for (int i = 0; i < coins.size(); ++i) { int tmp = coinChangeDFS(coins, target - coins[i], memo); if (tmp >= 0) memo[target] = min(memo[target], tmp + 1); } return memo[target] = (memo[target] == INT_MAX) ? -1 : memo[target]; } }; https://www.cnblogs.com/grandyang/p/5138186.htmlBest Time to Buy and Sell Stock(주식을 매매하기에 가장 좋은 시기) 영문:https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ 중국어 버전:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/ class Solution { public: int maxProfit(vector& prices) { if(prices.size()==0) return 0; int profit=0; int permin = prices[0]; for(int i=0;i Maximum Product Subarray(최대 서브시퀀스 곱하기) 영문:https://leetcode.com/problems/maximum-product-subarray/ 중국어 버전:https://leetcode-cn.com/problems/maximum-product-subarray/ class Solution { public: int maxProduct(vector& nums) { /* if(nums.size()==0) return 0; if(nums.size()==1) return nums[0]; int maxval=0; // 업로드를 통과하지 못했습니다: [-3,3,-8] 3이 돌아왔습니다. 72로 예상했습니다. 설마 -3과 8이 연속 서열?? for(int i=0;i Triangle(삼각형 최소 경로 및) 영문:https://leetcode.com/problems/triangle/ 중국어 버전:https://leetcode-cn.com/problems/triangle/ class Solution { public: int minimumTotal(vector>& triangle) { /* for (int i = 1; i < triangle.size(); ++i) { for (int j = 0; j < triangle[i].size(); ++j) { if (j == 0) { triangle[i][j] += triangle[i - 1][j]; } else if (j == triangle[i].size() - 1) { triangle[i][j] += triangle[i - 1][j - 1]; } else { triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]); } } } return *min_element(triangle.back().begin(), triangle.back().end());*/ vector dp(triangle.back()); for (int i = (int)triangle.size() - 2; i >= 0; --i) { for (int j = 0; j <= i; ++j) { dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]; } } return dp[0]; } };