CODEWITHSUNDEEP
c++algorithmdynamic-programmingdivide-and-conquer
Aryak Sengupta
Aryak Sengupta

Reputation: 1819

How to apply Dynamic Programming in SPOJ Feynman?

I was solving this problem -> http://www.spoj.com/problems/SAMER08F/ (A very simple problem) ... Got AC at my first go... My solution was like this (pretty straight-forward) :

#include<iostream>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
    while(n!=0)
    {
    printf("%d",((n)*(n+1)*((2*n)+1))/6);
    printf("\n");
    scanf("%d",&n);
    }
    return 0;
}

I was going through this list http://ahmed-aly.com/Category.jsp?ID=33 and I found Feynman listed as a DP problem... I am a beginer in DP and cannot figure out how can this problem consists of sub-problems. Any help or hint in finding the recurrence relations will be very helpful.

Upvotes: 1

Views: 1093

Answers (2)

mubasshir00
mubasshir00

Reputation: 349

Just use simple DP. If you observe the pattern you can notice that if You take 1 square it possible to make 64 square. if you take 2 size square it is possible to make (8-1) = 7*7 = 49 size square . so you can follow -> (8*8) + (7*7) + ........+(1*1) 

int feyn[1000];
 long long Feynman(long long x)
 {
if(x==1)return 1 ;

feyn[x]= (x*x)+Feynman(x-1);

return feyn[x];

 }

Upvotes: 0

user1925405
user1925405

Reputation: 352

It's just a silly DP.
What you are doing here is   formula right?
Instead what you could do is create an array to hold the sum of squares (Let's call it sumSquares). Now, this is how you would fill the array:

  1. sumSquares[0] = 0; (The base case, sum of the squares of the first zero elements is zero).

  2. sumSquares[i] = sumSquares[i - 1] + formula (Sum of squares of i elements is the sum of squares of (i - 1) elements + square of the ith element)

And that's it! You iterate till n, and you have your answer stored at sumSquares[n] !

Upvotes: 1

Related Questions