CODEWITHSUNDEEP
algorithm
efewf
efewf

Reputation: 13

Dynamic Programming solving an algorithm

Using Dynamic Programming approach calculate the value H(7) for the function H defined so that H(1)=2, H(2)=3 and, for all integers i>2, we have: H(i)=H(i-2)-H(i-1)+2.

I have looked up, watch videos and read about Dynamic Programming. But still struggling with the above question. I understand you solve the main problem by solving smaller problems beforehand. You then have more chance of solving the main problem because you can refer to your previous founding. And these prior results you have found are passed into a result but this is what I can't do with this question.

H(1)=H(1-2)-H(1-1)+2.
H(2)=H(2-2)-H(2-1)+2.
H(3)=H(3-2)-H(3-1)+2.
H(4)=H(4-2)-H(4-1)+2.
H(5)=H(5-2)-H(5-1)+2.
H(6)=H(6-2)-H(6-1)+2.

I'm presuming the simple computation of these should be put into a table and then I'm somehow supposed to use this information to then work out H(7).

Am I getting the complete wrong idea or doing it correctly, I don't know =[ Also this is revision for finals.

Upvotes: 1

Views: 130

Answers (4)

fkdosilovic
fkdosilovic

Reputation: 116

Your task is similiar to fibonnaci :) First i will explain you fibonacci.

F(1) = 1
F(2) = 1
F(N) = F(N - 1) + F(N - 2) , for every N > 2

First few fibonacci numbers:
F(1) = 1
F(2) = 1
F(3) = F(2) + F(1) = 2
F(4) = F(3) + F(2) = 3
F(5) = F(4) + F(3) = 5
...

You can see more on: http://en.wikipedia.org/wiki/Fibonacci_number

Fibonacci sequence of Fibonacci numbers is defined by the recurrence relation. Fibonacci sequence is recursive sequence.

Every recursion must have:
1) base case(s)
2) recurrence relation

In case of Fibonacci, base cases are: F(1), which equals 1 and F(2) which also equals 1. Recurrence relation is relation that "connects" smaller instances of the same problem. In case of Fibonacci numbers if you wanna know F(N) , you have to know F(N - 1) and F(N - 2), for all N > 2, and thats it. In case of Fibonacci, recurrence relation is F(N) = F(N - 1) + F(N - 2).

Here is code:

#include <cstdio>
#include <cstdlib>

using namespace std;

int f(int n) {

    //printf("n = %d\n", n);
    if(n == 1 || n == 2) // base case
        return 1;
    return f(n - 1) + f(n - 2); // recurrence relation

}

int main() {

    int n; scanf("%d", &n);
    printf("%d\n", f(n));

    return 0;
}

If you remove printf that is commented you will see that many values of Fibonacci are computed over and over again and that is very inefficient. Try running this code for F(45), and you will see why it's very inefficient.

This is where dynamic programming comes in. As you can see, many fibonacci values are computed over and over again, and we can use memoization to save them in table and if we need them we can just return them from table. Here is code:

#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;
const int N = 50;

long long memo[N];

long long f(int n) {
    if(memo[n] != -1) // if we already computed the value of f(N), then return that value
        return memo[n];
    return memo[n] = f(n - 1) + f(n - 2); // else compute the value, and save it into the table
}

int main() {

    memset(memo, -1, sizeof(memo));

    memo[1] = memo[2] = 1; // add answer for base case to the table

    int n; scanf("%d", &n);
    printf("%lld\n", f(n));

    return 0;
}

And finnaly, your question.

As Fibonacci, you can save the computed value of h(N). Here is a code:

#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;
const int N = 25;

int check, memo[N];

int f(int x) {
    if(memo[x] != check) // if f(n) was already computed
        return memo[x]; // return computed value
    return memo[x] = f(x - 2) - f(x - 1) + 2; // else compte given value and add it to a table
}

int main() {

    memset(memo, 63, sizeof(memo)); // very big number, if the value of h(n) is different then that very big number, then we know we have computed the value for h(n)
    check = memo[0];

    memo[1] = 2; // base case
    memo[2] = 3; // base case

    int n; scanf("%d", &n);
    printf("%d\n", f(n));

    return 0;
}

Upvotes: 3

t3s0
t3s0

Reputation: 282

H(1) = 2
H(2) = 3
H(3) = H(1) - H(2) + 2 = 2 - 3 + 2 = 1
H(4) = H(2)- H(3) + 2 = 3 - 1 + 2 = 4
H(5) = H(3) - H(4) + 2 = 1 - 4 + 2 = -1
H(6) = H(4) - H(5) + 2 = 4 - (-1) + 2 = 7
H(7) = H(5) - H(6) + 2 = -1 - 7 + 2 = -6
So H(7) is -6

Upvotes: 1

Matt
Matt

Reputation: 20796

Open up the JavaScript console in your browser, and type in:

function H(i) { return i==1 ? 2 : i==2 ? 3 : H(i-2)-H(i-1)+2 }

then

H(7)

which returns

-6

Upvotes: -1

user3386109
user3386109

Reputation: 34839

You were given

H(1)=2
H(2)=3

From that information, and the formula for H(i), you can compute H(3) as follows

H(3) = H(3-2) - H(3-1) + 2 = H(1) - H(2) + 2 = 2 - 3 + 2 = 1

Rinse and repeat.

Upvotes: 1

Related Questions