2 ms·
That was my first thought too. I thought the page was referring to DP/Memoization[1], initially. Thats the most useful concept I learnt about a decade back, and
by aws_ls 10y ago
That was my first thought too. I thought the page was referring to DP/Memoization[1], initially. Thats the most useful concept I learnt about a decade back, and was fortunate to be able to find a case in real-life to apply it.
I have often a hard time explaining it though. But very simply (the way I explain) it is, you compute and keep lot of results for lower values e.g. value of f(x,y) where x,y are less than some larger n,m respectively. And for computing f(n,m) you would need to compute f(x,y) a number of times for varying values of x,y. So if you keep it in memory. You save hell lot of a computing time. And your program runs in a fraction of time of what it would take other wise.
[1] https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/ https://www.topcoder.com/community/data-science/data-science...
Edit: minor correction
- wfunction 10y agoThe thing is, there is no stipulation that the subproblems be any "smaller" than the original problem. They just need to be instances of the same problem combining together in a manner that solves the original problem.
- aws_ls 10y agoYes, I can think of a case where how it may be used to solve some problems on a M x N grid, where in you could move in either directions top-left to bottom-right Or vice-versa. I perhaps used smaller where subproblem may be a more optimal use.