SPOJ SAMER08F

general
,
1

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??

2

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:

3

Thanks a lot. certainly helped me. :slight_smile:

4

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