[알고리즘] 리트코드 45. 점프 게임 II c++ // dp, 그리디 bfs

* 나의문제점 : 너무 그리디로 접근하려고함

그리디는 최후의 수단임.

완탐-> 완탐dp -> pq,정렬 -> 이분탐색 ->  ... -> 그리디 순으로 접근하는게 맞음.

 

* 완탐

 

* 완탐 + dp

int dp[10000+4];
vector<int> nums;

class Solution {
public:
    int jump(vector<int>& _nums) {
        memset(dp,-1,sizeof(dp));
        nums=_nums;
        return dfs(0);
    }

    int dfs(int pos){
        if(pos>=nums.size()-1){
            return 0;
        }
        if(dp[pos]!=-1) return dp[pos];

        dp[pos]=10001; //도달할수없는값
        for(int j=1;j<=nums[pos];++j){ //모든 점프가능한곳에대해
            dp[pos]=min(dp[pos],dfs(pos+j)+1);
        }
        return dp[pos];
    }
};

dp[pos] = min()이부분이 어떻게 작동하는지 반드시 알아야함!

 

* 그리디 + bfs?

이걸 O(N)에 푸는 이런게 가능하다니..