anshu2002's blog

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

• +4

 » 7 months ago, # |   0 Auto comment: topic has been updated by anshu2002 (previous revision, new revision, compare).
 » 7 months ago, # |   +5 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, # ^ |   0 thanks bro , I got it . #longlivecodingcommunity
 » 7 months ago, # |   0 Thankyou all critics