anshu2002's blog

By anshu2002, history, 2 years ago, In English
class Solution {
public:
    vector<vector<long long>>dp;
    void solve(int m, int n){
        for(int i=1;i<=m/2;i++){
            solve(i,n);
            solve(m-i,n);
            dp[m][n]=max(dp[m][n],dp[i][n]+dp[m-i][n]);
        }
        for(int i=1;i<=n/2;i++){
            solve(m,i);
            solve(m,n-i);
            dp[m][n]=max(dp[m][n],dp[m][i]+dp[m][n-i]);
        }
    }
    long long sellingWood(int m, int n, vector<vector<int>>& prices) {
        dp = vector<vector<long long>>(m+1,vector<long long>(n+1,0));
        for(auto it:prices){
            dp[it[0]][it[1]]=it[2];
        }
        solve(m,n);
        return dp[m][n];
    }
};

this was my approach , showing tle . Why ?? link to the problem

Please somebody correct my mistake

  • Vote: I like it
  • +4
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Use memorization. When you know optimal price for some piece (i.e. at the end of solve), make note of that fact and check at the beginning of solve whether or not you already know the optimal price (and thus don't need to go through the recursive part). That way any piece that you already encountered before will be solved in O(1).