Hello guys, this is my first post, and yes, it is asking for some help.
I am trying to solve this problem using dp. I know there is a greedy solution, but I would really like to solve it using dp. The thing is that the solution I devised uses 1000*1000*1000 in space.
Does anyone know a better way to solve it using dp.
Thanks for your help.
I think we can define dp1[i][j] as the maximum profit if we put kth~(j-1)th people into ith plane, where (j-k)<=a[i], k>=1 (if k==j,then we don't put any people into ith plane) dp2[i][j] can be defined as the minimum profit as the max profit
dp1[1][j] = a[i]+(a[i]-1)+...+(a[i]-j+2) for 1<=j<=a[i]+1 dp1[i][j] = max(dp1[i-1,j],dp1[i-1][j-k]+(a[i]+...+(a[i]-k+1)) for 1<=k<=a[i] and 1<=j<=m+1
finally obtain dp1[n][m+1] and output it. Not completely sure about this solution but it may work with O(nm^2) time and O(nm) space complexity. Surely annoying implementation.
Since the post is tagged dp , I felt this to be a right place to ask my query ... Many of the coders on codeforces are outstanding in dynamic programming but I am still a beginner in it . I know what dynamic programming is and how it works in different contexts , but I find it hard to implement it into problems . Can someone please suggest me some ways to overcome this difficulty . Any sugggestions would be welcomed !!!