How to apply Dynamic Programming in SPOJ Feynman?

Question

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.

Answer 1

It's just a silly DP.
What you are doing here is    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] + (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] !