title: Understanding subtleties of dynamic programming approaches
body: <p>I understand that there are mainly two approaches to dynamic programming solutions:</p>
  <ol>
  <li><p><strong>Fixed optimal order of evaluation</strong>  (lets call it <strong>Foo approach</strong>): Foo approach usually goes from subproblems to bigger problems thus using results obtained earlier for subproblems to solve bigger problems, thus <strong>avoiding &quot;revisiting&quot;</strong> subproblem. <a href="https://en.wikipedia.org/wiki/Introduction_to_Algorithms" rel="nofollow noreferrer">CLRS</a> also seems to call this <strong>&quot;Bottom Up&quot;</strong> approach.</p>
  </li>
  <li><p><strong>Without fixed optimal order of evaluation</strong> (lets call it <strong>Non-Foo approach</strong>): In this approach evaluation proceeds from problems to their sub-problems . It ensures that sub problems are <strong>not &quot;re-evaluated&quot;</strong> (thus ensuring optimality) by maintaining results of their past evaluations in some data structure and then first checking if the result of the problem at hand exists in this data structure before starting its evaluation. CLRS seem to call this as <strong>&quot;Top Down&quot;</strong> approach</p>
  </li>
  </ol>
  <p>This is what is roughly conveyed as one of the main points by <a href="https://stackoverflow.com/a/6165124/1317018">this</a> answer.</p>
  <p>I have following doubts:</p>
  <h3>Q1. Memoization or not?</h3>
  <hr />
  <p>CLRS uses terms &quot;top down <em>with memoization</em>&quot; approach and &quot;bottom up&quot; approach. I feel both approaches require memory to cache results of sub problems. But, then, why CLRS use term &quot;memoization&quot; only for top down approach and not for bottom up approach? After solving some problems by DP approach, I feel that solutions by top down approach for <strong>all</strong> problems require memory to caches results of <strong>&quot;all&quot;</strong> subproblems. However, that is not the case with bottom up approach. Solutions by bottom up approach for <strong>some</strong> problems does not need to cache results of <strong>&quot;all&quot;</strong> sub problems. <strong>Q1.</strong> Am I correct with this?</p>
  <p>For example consider <a href="https://leetcode.com/problems/min-cost-climbing-stairs/" rel="nofollow noreferrer">this problem</a>:</p>
  <blockquote>
  <p>Given <code>cost[i]</code> being the cost of <code>i</code>th step on a staircase, give the minimum cost of reaching the top of the floor if:</p>
  <ul>
  <li>you can climb either one or two steps</li>
  <li>you can start from the step with index 0, or the step with index 1</li>
  </ul>
  </blockquote>
  <p>The top down approach solution is as follows:</p>
  <pre><code>class Solution: 
      def minCostAux(self, curStep, cost):
  
          if self.minCosts[curStep] &gt; -1:
              return self.minCosts[curStep]
          
          if curStep == -1:
              return 0
          elif curStep == 0:
              self.minCosts[curStep] = cost[0] 
          else: 
              self.minCosts[curStep] = min(self.minCostAux(curStep-2, cost) + cost[curStep]
                                  , self.minCostAux(curStep-1, cost) + cost[curStep]) 
          
          return self.minCosts[curStep]
          
      def minCostClimbingStairs(self, cost) -&gt; int:
          cost.append(0)
          self.minCosts = [-1] * len(cost)
          return self.minCostAux(len(cost)-1, cost)
  </code></pre>
  <p>The bottom up approach solution is as follows:</p>
  <pre><code>class Solution:        
      def minCostClimbingStairs(self, cost) -&gt; int:
          cost.append(0)
          
          secondLastMinCost = cost[0]
          lastMinCost = min(cost[0]+cost[1], cost[1])
          
          minCost = lastMinCost
          
          for i in range(2,len(cost)):
              minCost = min(lastMinCost, secondLastMinCost) + cost[i]
              secondLastMinCost = lastMinCost
              lastMinCost = minCost
          
          return minCost
  </code></pre>
  <p>Note that the top down approach caches result of <strong>all steps</strong> in <code>self.minCosts</code> while bottom up approach caches result of only <strong>last two steps</strong> in variables <code>lastMinCost</code> and <code>secondLastMinCost</code>.</p>
  <h3>Q2. Does all problems have solutions by both approaches?</h3>
  <hr />
  <p>I feel no. I came to this opinion after solving <a href="https://leetcode.com/problems/knight-probability-in-chessboard/" rel="nofollow noreferrer">this problem</a>:</p>
  <blockquote>
  <p>Find the probability that the knight will not go out of <code>n x n</code> chessboard after <code>k</code> moves, if the knight was initially kept in the cell at index <code>(row, column)</code>.</p>
  </blockquote>
  <p>I feel the only way to solve this problem is to find successive probabilities in increasing number of steps starting from cell <code>(row, column)</code>, that is probability that the knight will not go out of chessboard after step 1, then after step 2, then after step 3 and so on. This is bottom up approach. We cannot do it top down, for example, we cannot start with <code>k</code>th step and go to <code>k-1</code>th step, then <code>k-2</code>th step and so on, because:</p>
  <ol>
  <li>We cannot know which cells will be reached in <code>k</code>th step to start with</li>
  <li>We cannot ensure that all paths from <code>k</code>th step will lead to initial knight cell position <code>(row,column)</code>.</li>
  </ol>
  <p>Even one of the <a href="https://leetcode.com/problems/knight-probability-in-chessboard/discuss/113954/Evolve-from-recursive-to-dpbeats-94" rel="nofollow noreferrer">top voted answer</a> gives dp solution as follows:</p>
  <pre><code>class Solution {
      private int[][]dir = new int[][]{{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};
      private double[][][] dp;
      public double knightProbability(int N, int K, int r, int c) {
          dp = new double[N][N][K + 1];
          return find(N,K,r,c);
      }
      public double find(int N,int K,int r,int c){
          if(r &lt; 0 || r &gt; N - 1 || c &lt; 0 || c &gt; N - 1) return 0;
          if(K == 0)  return 1;
          if(dp[r][c][K] != 0) return dp[r][c][K];
          double rate = 0;
          for(int i = 0;i &lt; dir.length;i++)   rate += 0.125 * find(N,K - 1,r + dir[i][0],c + dir[i][1]);
          dp[r][c][K] = rate;
          return rate;
      }
  }
  </code></pre>
  <p>I feel this is still a bottom up approach since it starts with initial knight cell position <code>(r,c)</code> (and hence starts from <code>0</code>th or no step to <code>K</code>th step) despite the fact that it counts <code>K</code> downwads to 0. So, this is bottom up approach done recursively and not top down approach. To be precise, this solution <strong>does NOT first find</strong>:</p>
  <ul>
  <li>probability of knight not going out of chessboard after <code>K</code> steps starting at cell <code>(r,c)</code></li>
  </ul>
  <p>and then find:</p>
  <ul>
  <li>probability of knight not going out of chessboard after <code>K-1</code> steps <strong>starting at cell <code>(r,c)</code></strong></li>
  </ul>
  <p>but it finds in reverse / bottom up order: first for <code>K-1</code> steps and then for <code>K</code> steps.</p>
  <p>Also, I did not find any solutions in of <a href="https://leetcode.com/discuss/interview-question?currentPage=1&amp;orderBy=hot&amp;query=" rel="nofollow noreferrer">top voted discussions in leetcode</a> doing it in truly top down manner, starting from <code>K</code>th step to <code>0</code>th step ending in <code>(row,column)</code> cell, instead of starting with  <code>(row,column)</code> cell.</p>
  <p>Similarly we cannot solve the following problem with the bottom up approach but only with top down approach:</p>
  <blockquote>
  <p>Find the probability that the Knight ends up in the cell at index <code>(row,column)</code> after K steps, starting at any initial cell.</p>
  </blockquote>
  <p><strong>Q2.</strong> So am I correct with my understanding that not all problems have solutions by both top down or bottom up approaches? Or am I just overthinking unnecessarily and both above problems can indeed be solved with both top down and bottom up approaches?</p>
  <p><strong>PS:</strong> I indeed seem to have done overthinking here: <code>knightProbability()</code> function above is indeed top down, and I ill-interpreted as explained in detailed above . I have kept this explanation for reference as there are already some answers below and also as a hint of how confusion / mis-interpretaions might happen, so that I will be more cautious in future. Sorry if this long explanation caused you some confusion / frustrations. Regardless, the main question still holds: does every problem have bottom up and top down solutions?</p>
  <h3>Q3. Bottom up approach recursively?</h3>
  <hr />
  <p>I am pondering if bottom up solutions for all problems can also be implemented recursively. After trying to do so for other problems, I came to following conclusion:</p>
  <blockquote>
  <p>We can implement bottom up solutions for such problems recursively, only that the recursion won't be meaningful, but kind of hacky.</p>
  </blockquote>
  <p>For example, below is recursive bottom up solution for <a href="https://leetcode.com/problems/min-cost-climbing-stairs/" rel="nofollow noreferrer">minimum cost climbing stairs problem</a> mentioned in Q1:</p>
  <pre><code>class Solution:   
      def minCostAux(self, step_i, cost):
          if self.minCosts[step_i] != -1:
              return self.minCosts[step_i]
              
          self.minCosts[step_i] = min(self.minCostAux(step_i-1, cost)
                                      , self.minCostAux(step_i-2, cost)) + cost[step_i]
  
          if step_i == len(cost)-1: # returning from non-base case, gives sense of 
                                    # not-so meaningful recursion.
                                    # Also, base cases usually appear at the 
                                    # beginning, before recursive call.
                                    # Or should we call it &quot;ceil condition&quot;?
              return self.minCosts[step_i]
  
          return self.minCostAux(step_i+1, cost)
      
      def minCostClimbingStairs(self, cost: List[int]) -&gt; int:
          cost.append(0)
  
          self.minCosts = [-1] * len(cost)
  
          self.minCosts[0] = cost[0]
          self.minCosts[1] = min(cost[0]+cost[1], cost[1])
          
          return self.minCostAux(2, cost)
  </code></pre>
  <p>Is my quoted understanding correct?</p>