[CSE 565] - DP - Easy Task vs Hard Task

 

 

n days 가 있고

 

easy task -> ak 를 준다  k는 1<= k <= n 

 

hard task -> bk를 준다 k는 1<= k <= n 이다

 

아무것도 안하면 그냥 reward를 준다

 

hard task 를 k day에 하면  1<= k < = n, k+1에 일을 하면 안된다. 

 

ak 랑 bk가 주어지면 알고리즘을 짠다 -> 그래서 total rewards가 maximize 되야 한다

 

여기서 확실하게 알수있는건

 

a(k) 는 ai = max{(a(i-1) + ai} 일 것이다 i <= k < n

 

b(k) 는 bi = max{a(i-1) + bk, b(i-2) + bk }

 

이거인거 같은데 

 

즉 이 둘 중에서 

 

max를 고르면 된다. 

 

max (high[i] + max_task(high,low, i-2)), low[i] + max_task(high,low,(i-1))

 

award_array - 맥시멈으로 얻을 수 있는 양

 

초기화 - 처음에 award_array 를 다 0으로 한다.

 

task_dp[0] = 0 이다 

 

n = 1 이라면 award_array[1] = max{a0, b0}

 

award_array[i] = max{ak[i-1] + award_array[i-2], bk[i-1] +award_array[i-1]}

 

Termination = award_array[n] 를 return 하면 된다. 

 

Time Complexity = O(n)

 

Subproblems O(n)  Time complexity - 이렇게 하면 된다. 

 

정리를 해보면 이렇게 된다.