PROBLEM LINK:
Author: Dr. Mustaq Ahmed
Tester: Jingbo Shang
Editorialist: Jingbo Shang
DIFFICULTY:
Easy - Medium
PREREQUISITES:
Dynamic Programming
PROBLEM:
Given a M×N matrix Price (M days, N types) indicating the price of each model of hard disk on each day, find out the minimum cost to have exact one disk per day. The price of selling an older one is 100 less than the current buying price.
EXPLANATION:
Let’s use OPT[D][T] to state the minimum cost if D days passed and we have disk T in the end.
From this state, we can enumerate the next selling/buying day D’ and the new model T’. That is,
OPT[D’][T’]= Price[D’][T’]+min_(D<D’,T’≠T){OPT[D][T]–Price[D’][T]+100}
This dynamic programming is O(N^2 M^2), which will get TLE.
We should observe that if we known T, we will definitely choose min_(D<D’) {OPT[D][T]}, denoted as G[D’][T]. Therefore, we can use this G[][] array to optimize the solution to O(N^2 M)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.