SPOJ SAMER08F

I solved this question using the standard formula, but i want to solve this question using dynamic programming as i am newbie. Problem Link: http://www.spoj.com/problems/SAMER08F/ could anyone suggest me how to proceed using dp??

Just check out the relation between the answer for consecutive numbers and then represent it in that form. Now try it yourself and then ask again if you have a doubt.
Happy coding! :slight_smile:

Thanks a lot. certainly helped me. :slight_smile:

Here is the c solution that i solved using DP

#include <stdio.h>
#include <stdlib.h>
 
 long sizes[101];
 long getNumperOfSquers(int n) {
        if (n == 1)
            return 1;
        else if (sizes[n] != 0)
            return sizes[n];
 
            sizes[n] = n*n + getNumperOfSquers(n-1);
        return sizes[n];
    }
 
int main()
{
        int n = 0;
        scanf("%d",&n);
        while (n != 0) {
            printf("%ld\n",getNumperOfSquers(n));
            scanf("%d",&n);
        }
    return 0;
}

And here is the c++ version

#include<iostream>
using namespace std;
static long a[100];

int get(int i){
    int t;
    t=i;
    if(i==1){
        return 1;
    }
    for(int h=1; h<=i; h++){
        if(a[i]!=0){
            return a[i];
        }
        a[h]=h*h+a[h-1];
    }
    return a[i];
}

int main(){
    int a;
    do{
        int b=0;
        cin>>a;
        if(a!=0){
            b=get(a);
            cout<<b<<endl;
        }
    }while(a!=0);

}
3 Likes
//