anshu2002's blog

By anshu2002, history, 7 months 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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by anshu2002 (previous revision, new revision, compare).

»
7 months 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).

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks bro , I got it . #longlivecodingcommunity

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thankyou all critics