스크롤 그룹 기초

1690 단어
스크롤 그룹을 이용하면 N이 큰 상황에서 압축 저장 작용을 할 수 있다.그러나 DP 문제에서 자주 사용된다. 왜냐하면 DP 문제는 아래에서 위로 확장되는 과정이기 때문에 우리는 연속적인 풀이를 자주 사용한다. 앞의 풀이는 종종 포기한다!그래서 스크롤 그룹을 사용하는 것은 매우 필요하다고 말할 수 있다.
스크롤 배열의 간단한 예:
int i, d[100];
d[0] = 1;
d[1] = 1;
for (i = 2; i < 100; i++)
    d[i] = d[i - 1] + d[i - 2];
printf("%d", d[99]);

위의 이 순환 d[i]는 앞의 두 데이터 d[i-1]와 d[i-2]에만 의존한다.
공간을 절약하기 위해 스크롤 그룹을 사용하는 방법:
int d[3];
d[0] = 1;
d[1] = 1;
for (i = 2; i < 100; i++)
    d[i % 3] = d[(i - 1) % 3] + d[(i - 2) % 3];
printf("%d", d[99 % 3]);

위의 잉여 연산을 주의하십시오. 우리는 필요한 마지막 세 개의 해만 성공적으로 보존했습니다. 수조는 '스크롤' 과 같아서 스크롤 수조라고 합니다.
//DP는 2D에서도 사용할 수 있습니다(코드가 정확하고 완벽하지 않을 수 있지만 예는 이해할 수 있습니다).
int i,j,d[100][100];
for(i=1;i<100;i++)
    for(j=0;j<100;j++)
        d[i][j]=d[i-1][j]+d[i][j-1];

위의 d[i][j]는 d[i-1][j], d[i][j-1]에만 의존한다.
스크롤 그룹 사용하기
int i,,j,d[2][100];
for(i=1;i<100;i++)
    for(j=0;j<100;j++)
        d[i%2][j]=d[(i-1)%2][j]+d[i%2][j-1];

동수조는 실제적으로 공간을 절약하는 방법으로 시간적으로 우세가 없다. 주로 DP에 사용된다.
예:
DP 1개, 일반적으로 1000 필요×1000 공간, DP의 비후효성에 따라 2×1000, 그리고 스크롤, 획득 및 1000×1000 같은 효과.스크롤 그룹은 DP에 많이 사용된다. DP 과정에서 우리가 한 상태에서 다른 상태로 전환할 때 이전에 저장된 일부 상태 정보가 무용지물일 가능성이 높다. 예를 들어 01배낭 문제에서 이해의 측면에서 볼 때 우리는 DP[i][j]의 2차원 그룹을 열어야 한다. 1차원에서 우리는 몇 개의 물품, 즉 단계, 2차원 저장 용량을 저장해야 한다. 그러나 우리는 DP[i]를 얻고 DP[i-1]의 정보를 사용하기만 하면 된다.DP[i-k], k>1은 모두 쓸모없는 공간이 되었기 때문에 우리는 수조를 1차원으로 열면 된다. 수조의 내용을 교체하고 수조를 굴리는 것도 이 원리이다. 목적도 마찬가지다. 그러나 이때의 문제는 1차원으로 축소할 수 없다. 예를 들어 하나의 DP[i][j]는 DP[i-1][k], DP[i-2][k]로 결정해야 한다. i
#2 익스프레스 서버에 graphql 추가하기
[Android] NavigationDrawer를 오른쪽에 표시

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage