CODEWITHSUNDEEP
algorithmdynamic-programming
Harsha Reaper
Harsha Reaper

Reputation: 129

Can someone suggest a dynamic programming solution to solve this?

I'm trying to get better at DP and have been going through some practice problems. Please have a look at this one. I'm able to barely think of a solution to it but it's just in bits and pieces. I'm not able to connect them together and come up with a proper algorithm. How would one solve this efficiently through dynamic programming? P.S. This is not part of an on-going contest or any kind of assignment. It's just a practice problem from a past contest.

Brief problem description:

You're given 'n' number of discs of varying height and radius. You have to build the tallest tower possible using those discs in such a way that for each of those discs, both it's radius and height are smaller than the radius and height of the disc below it respectively.

What I tried:

I have an array dp[1....n] where dp[i] (1<=i<=n) stores the height of the tallest tower you can build using only the discs in the range 1....i. Then for disc i+1, there are two options. I either use it or I don't. So I iterate from 1 to i and add the heights of all discs whose dimensions don't conflict with disc i+1. Then i pick the bigger among that sum + height of disc i+1 and dp[i] and store it in dp[i+1]. Obviously, this does not work for some cases. I'm not checking if any of the other discs I picked are conflicting among themselves. Not sure if it's understandable but this is the best I can explain it.

Upvotes: 2

Views: 321

Answers (2)

Zoomba
Zoomba

Reputation: 1806

Since it is dynamic programming you have to see when the situation is repeated. Here if the radius/height that you are allowed to use is the same is before then the answer is the same. Besides, since the problem says it is "smaller than" you don't have to worry about using a disc twice. Since using the same disc twice will be ruled out automatically.

int dp(int allowed_rad, int allowed_height){
    if(memo[allowed_rad][allowed_height] == true) //I alread have the answer
        return dp[allowed_rad][allowed_height];
    memo[allowed_rad][allowed_height] = true;

    dp[allowed_rad][allowed_height] = 0; //Initiallizing with zero

    int ret = 0;
    for(int i = 0; i < n; i++){
        if(rad[i] < allowed_rad && height[i] < allowed_height){
            int result = height[i] + dp(rad[i], height[i]);
            if(result > ret) ret = result;
        }
    }

    //it is possible that 0 is returned if I don't have any more option
    return dp[allowed_rad][allowed_height] = ret;
}

Upvotes: 1

uSeemSurprised
uSeemSurprised

Reputation: 1834

You have the right approach you just need to sort the pair of heights and radius, once you have done that a O(n^2) solution is possible.

At each index you can either take or leave the current element based on the fact that what was the previous element that you selected, you will compare with all the previous elements from 0 to i-1 for the current element i.

I have written a simple recursive DP code in c++ :

#include<bits/stdc++.h>
using namespace std;

int n;
vector< pair<long long, long long> > val;
long long dp[300][300];

long long solve(int idx, int prev){
    if(idx == n+1) return 0;
    if(dp[idx][prev] != -1) return dp[idx][prev];
    //do not choose current element
    long long ans = solve(idx+1, prev);

    //try to choose current element
    if(val[idx].first > val[prev].first && val[idx].second > val[prev].second){
        ans = max(ans, solve(idx+1, idx) + val[idx].second);
    }
    return dp[idx][prev] = ans;
}

int main(){
    int t;cin >> t;
    while(t--){
        cin >> n;
        long long rad, ht;
        val.clear();
        val.push_back(make_pair(0, 0));
        for(int i = 0;i < n;i++) cin >> rad >> ht, val.push_back(make_pair(rad, ht));
        for(int i = 0;i < 300;i++) for(int j = 0;j < 300;j++) dp[i][j] = -1;
        sort(val.begin(), val.end());
        cout << solve(1, 0) << endl;
    }
    return 0;
}

Upvotes: 2

Related Questions