title: how to solve the overlapping sub problems in Dynamic programming
body: <p>Problem statement =&gt;</p>
  <p>You are given  queries. Each query consists of a single number N. You can perform any of the 2 operations on  in each move:</p>
  <p>1: If we take 2 integers a and b where N=a*b (a&gt;1,b&gt;1), then we can change N=max(a,b).</p>
  <p>2: Decrease the value of N by 1.</p>
  <p>Determine the minimum number of moves required to reduce the value of N to 0.</p>
  <p>here is the link for better understanding.
  <a href="https://www.hackerrank.com/challenges/down-to-zero-ii/problem" rel="nofollow noreferrer">https://www.hackerrank.com/challenges/down-to-zero-ii/problem</a></p>
  <p>I know here are some overlapping sub-problems and we can use DP to ignore the computation of same sub-problems again and again.</p>
  <p>Now, my question is how in this problem, same sub-problems have same solutions. Because we have to solve this from top to bottom and sub-problem have same solution if we solved them from bottom to top.</p>
  <p>For example</p>
  <pre><code>N=4
  1 possibility = 4-&gt;3-&gt;2-&gt;1-&gt;0
  2 possibility = 4-&gt;2-&gt;1-&gt;0
  </code></pre>
  <p>Now in above two possibility, 2 is repeating and I can use DP, but how I store their values. I mean, in 1 possibility solution of 2 is different from 2nd possibility because in first one I've to traverse 4-&gt;3-&gt;2 here solution of 2 is 2 and in 2nd possibility we traverse 4-&gt;2 and solution of 2 here is 1 now these 2 same sub-problems have different values because of the solving from top to bottom. Now I'm totally confused here. Please someone help me out in this.</p>