質問する

に答える

ソリューション

dp[i]=max(p[i]+dp[t[i]+i]],max_value)dp[i] = max(p[i] + dp[t[i]+i]], max\_value)dp[i]=max(p[i]+dp[t[i]+i]],max_value)

dp[i]=i 1日目から最終日までの最大利益

max value=後から計算される変数

は、これまでの最大コンサルティング金額に相当する
後から後まで、各コンサルティング(現在のコンサルティング日の利益p[i]+現代コンサルティング終了日からの最大利益dp[t[i]+i)について算出する.次に計算される各値から最上位値を抽出

に感銘を与える

これは私が最近アルゴリズムを解いたときに感じたことです.
想像もつかない変なアルゴリズムで乾杯!解くというより.
基本的にはすべての状況を計算します.
これはどんなアルゴリズムで改善された問題だと思います.
DPも計算を部分的に分けて、分割した部分を再利用して改善する、そんな壮大な点火式!新しい!数学!違うみたい...(気まずい)

に答える

コミットコード

n = int(input()) # 전체 상담 갯수
t = []
p = []
dp = [0] * (n+1) # dynamic programming을 위한 1차원 dp 테이블 초기화
max_value = 0 #뒤에서부터 계산할때, 현재까지의 최대 상담 금액에 해당하는 변수

for _ in range(n) :
	x, y = map(int, input().split())
	t.append(x)
	p.append(y)

# 리스트를 뒤에서부터 거꾸로 확인
for i in range(n-1, -1, -1) :
	time = t[i] + i
	# 상담이 기간 안에 끝나는 경우
	if time <= n :
		# 점화식에 맞게, 현재까지의 최고 이익 계산
		dp[i] = max(p[i] + dp[time], max_value)
		max_value = dp[i]
	# 상담이 기간을 벗어나는 경우
	else :
		dp[i] = max_value

print(max_value)

出力コードの理解