title: Reaching from first index to last with minimum product without using Graphs?
body: <p>Solving this <a href="https://www.codechef.com/problems/CHRL4" rel="nofollow">problem</a> on codechef:</p>
  
  <blockquote>
    <p>After visiting a childhood friend, Chef wants to get back to his home.
    Friend lives at the first street, and Chef himself lives at the N-th
    (and the last) street. Their city is a bit special: you can move from
    the X-th street to the Y-th street if and only if 1 &lt;= Y - X &lt;= K,
    where K is the integer value that is given to you. Chef wants to get
    to home in such a way that the product of all the visited streets'
    special numbers is minimal (including the first and the N-th street).
    Please, help him to find such a product. Input</p>
    
    <p>The first line of input consists of two integer numbers - N and K -
    the number of streets and the value of K respectively. The second line
    consist of N numbers - A1, A2, ..., AN respectively, where Ai equals
    to the special number of the i-th street. Output</p>
    
    <p>Please output the value of the minimal possible product, modulo
    1000000007. Constraints</p>
    
    <p>1 ≤ N ≤ 10^5 1 ≤ Ai ≤ 10^5 1 ≤ K ≤ N Example</p>
    
    <p>Input: 4 2 1 2 3 4.</p>
    
    <p>Output: 8</p>
  </blockquote>
  
  <p>It could be solved using <strong>graphs</strong> based on this <a href="https://discuss.codechef.com/questions/37605/chrl4-editorial" rel="nofollow">tutorial</a>
  I tried to solve it without using graphs and just using <strong>recursion</strong> and <strong>DP</strong>.
  My approach:</p>
  
  <ol>
  <li>Take an array and calculate the min product to reach every index and store it in the respective index.</li>
  <li>This could be calculated using top down approach and recursively sending index (eligible) until starting index is reached.</li>
  <li>Out of all calculated values store the minimum one.</li>
  <li>If it is already calculated return it else calculate. </li>
  </ol>
  
  <p>CODE:</p>
  
  <pre><code> #include&lt;iostream&gt;
   #include&lt;cstdio&gt;
   #define LI long int
   #define MAX 100009
   #define MOD 1000000007
   using namespace std;
   LI dp[MAX]={0};
   LI ar[MAX],k,orig;
   void cal(LI n)
   {
         if(n==0)
            return;
         if(dp[n]!=0)
            return;
         LI minn=MAX;
         for(LI i=n-1;i&gt;=0;i--)
         {
            if(ar[n]-ar[i]&lt;=k &amp;&amp; ar[n]-ar[i]&gt;=1)
            {
                cal(i);
                minn=(min(dp[i]*ar[n],minn))%MOD;
            }
         }
         dp[n]=minn%MOD;
         return;
   }
  
   int main()
   {
      LI n,i;
      scanf("%ld %ld",&amp;n,&amp;k);
      orig=n;
      for(i=0;i&lt;n;i++)
         scanf("%ld",&amp;ar[i]);
      dp[0]=ar[0];
      cal(n-1);
      if(dp[n-1]==MAX)
         printf("0");
      else printf("%ld",dp[n-1]);
      return 0;
  }
  </code></pre>
  
  <p>Its been 2 days and I have checked every corner cases and constraints but it still gives Wrong answer! Whats wrong with the solution? </p>
  
  <p>Need Help. </p>