leetcode 점프 게임

1500 단어 동적 기획
음수가 아닌 정수 그룹을 지정합니다. 그룹의 첫 번째 위치에 있습니다.
수조의 모든 원소는 당신이 이 위치에서 점프할 수 있는 최대 길이를 대표합니다.
너의 목표는 가장 적은 점프 횟수를 사용하여 수조의 마지막 위치에 도달하는 것이다.
예:
  : [2,3,1,1,4]
  : 2
  :                 2。
     0       1    ，  1 ，    3             。

1. 동적 계획 시간 초과
만약 입력 수조가num이라고 가정하고, 수조 dp[i]로 i번째 위치에 도달하는 데 필요한 최소 걸음수를 표시하면
$$dp[i] =\min\{dp[j]|0\leq j
C++ 구현
int min_jump(vector num)
{
    int n = num.size();
    vector dp(n, 0);
    dp[0] = 0;
    for(int i=1;i= i)
                    min_ = dp[j]
            }
        dp[i] = min_ + 1;
    }
    return dp[n - 1];
}

2. 욕심
매번 다음 단계에서 가장 멀리 뛸 수 있는 위치로
C++ 구현
int min_jump(vector num)
{
    int n = num.size();
    if(n<=1)
        return 0;
    for(int i=0;i=n - 1)
        {
            step++;
            break;
        }
        int max_jump = 0;
        int max_index;
        for(int j=i;j<=num[i] + i;j++)
        {
            if(num[j] + j > max_jump)
            {
                max_jump = num[j] + j;
                max_index = j;
            }
        }   
        i = max_index;
        step++;
    }
    return step;
}

POJ-1185 포병 진지 동적 기획 + 상태 압축
커다란 필기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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