https://www.acmicpc.net/problem/14501
Initial approach
This wasn't the easy min. number of steps to reach a floor in Leetcode.
Solution
I think it is hard to
1) come up with what dp[i] will represent
2) the mathematical way of finding the relationship of DP
Bottom-up
https://great-park.tistory.com/48
I originally thought of backwards but it is possible bottom-up. Let dp[i] be the max profit possible when you work until the ith day.
As we iterate through the days, if we decide to take the consultation on that day and its profit on the ending day is bigger and worth than the recorded profit on that ending day, we override that profit.
n=int(input())
schedule = [list(map(int, input().split())) for _ in range(n)]
dp=[0 for _ in range(n+1)]
for i in range(n):
for j in range(i+schedule[i][0],n+1):
if dp[j]<dp[i]+schedule[i][1]:
dp[j]=dp[i]+schedule[i][1]
# if j>=n+1:
# dp[i]=dp[i-1]
# else:
# dp[i]= max(dp[i],dp[i-1]+schedule[i][1])
print( dp[-1])Then I thought, won't this go over the list when we choose a schedule from the ith day? No we don't have to consider that because our outer loop that iterates through i assumes that the current dp[i] holds the maximum profit gained if you worked till the ith day. So if we just decide if we do take this schedule on the ith day or not and we decide that based on if the so-far-recorded ending day's profit is smaller than today (i-th)'s accumulated profit + ith schedule's profit.
