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