[leetcode] 45. Jump Game II

class Solution {
public:
    int jump(vector<int>& nums) {
        vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));
        int minMove = INT_MAX;
        
        for(int i = 0; i<nums.size(); i++){
            minMove = INT_MAX;
            
            for(int j = 0; j<=i; j++){
                if(!dp[j][i]) continue;
                minMove = min(minMove, dp[j][i]);
            }
            
            minMove = minMove == INT_MAX ? 0 : minMove;
            int start = i + 1;
            int end = i + 1 + nums[i];
            
            for(int j = start; j<end; j++){
                if(j == dp.size()) break;
                dp[i][j] = minMove + 1;                
            }
        }
        
        return minMove;
    }
};

BF + 메모이제이션으로만 풀었습니다. 이렇게 풀어도 꽤나 괜찮은 성능을 뽑아냅니다.

시간복잡도 : O(N^2)

 

 

꽤나 괜찮은 성능이나 다른사람들의 풀이를 보니 역시 더 좋은 방법이 있더군요

그리디 방식으로 풀던데 요건 차후에,,