9도 1547 출입창(배달DP)
5006 단어 dp
처음에 비어 있는 창고와 n개의 작업으로 구성된 작업 순서를 지정합니다. 모든 작업은 출고나 입고일 수 있습니다.작업 시퀀스를 실행하는 과정에서 불법 작업이 발생하지 않도록 요구한다. 즉, 빈 창고에서 출고 작업을 실행하지 않을 뿐만 아니라 작업 시퀀스가 완성된 후에 창고가 꼭 빈 창고가 되도록 보장한다.조건에 부합되는 조작 시퀀스 종류를 구하다.예를 들어 4개의 작업으로 구성된 작업 순서는 다음과 같다. 입고, 출고, 입고, 입고, 입고, 입고, 출고, 총 2종이다.
사고의 방향
1.Leetcode에 비슷한 문제가 있는데 그 문제는 괄호의 총류를 구하고 애초에 검색법을 사용했다
2. 검색법 시간 초과, 분치법 좋은 방법 생각 안 나
3. dp[i][j](i>=j)는 입고 i회 출고 j회의 종류수를 나타낸다
4. dp[i][j] = dp[i-1][j] + dp[i][j-1]. 상태 이동 방정식에서 이러한 근거를 쓰는 것은 마지막 자리가 각각'('와')인 상황을 토론하는 데 있어야 한다.검지offer가 바닥을 깔아놓은 문제처럼.예를 들어 dp[3][2], 마지막 사람이'(''일 때 dp[3][2]=dp[2][2],')'로 확정될 때 dp[3][2]=dp[3][1].이렇게 보면 이 문제는 자신이 이전에 했던 많은 문제와 유사하다. 예를 들어 계단을 오르는 것, 예를 들어 네모난 칸으로 길을 찾는 등이다.이 문제들의 공통된 특징은 마지막 상태의 위치에 따라 앞의 모든 가능성을 점차적으로 미루는 것이다.
5.leetcode가 그 문제에 대응하는 것을 보고 그것이 인쇄 경로라는 것을 발견하여 검색법이 시간을 초과하지 않았습니다.
코드가 9도 테스트를 통과하지 못했다
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;
int dp[1200][1200];
int find(int a, int b) {
if(a < b)
return 0;
if(dp[a][b] != 0)
return dp[a][b];
if(a == 0 || b == 0)
return 0;
int res = find(a-1,b) + find(a,b-1);
if(res >= 1000000007 )
res = res%1000000007;
return (dp[a][b] = res);
}
int main() {
freopen("testcase.txt", "r", stdin);
int n;
memset(dp, 0, sizeof(dp));
for(int i = 0; i < 1010; i ++)
dp[i][0] = 1;
dp[1][1] = 1;
while(scanf("%d", &n) != EOF) {
int res = find(n/2,n/2);
printf("%d
", res);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
