Calculate g(1000) given the following definition of g function..

+1 vote
g(1) = g(2) = .. g(10) = 1

g(n) = g(n-1) + 3 *g(n-3) + 7*g(n-10)
asked Jun 8 in Dynamic Programming by Amrinder Arora (206 points)
recategorized Jun 16 by Amrinder Arora

2 Answers

+1 vote
This problem is very similar to the fib by using dynamic programming.

The solution is using tabulation.

memo=[1]*1001
memo[0]=0
def g(n):
    if n<=0:
        return memo[0]
    elif n<=10:
        return memo[n]
    for i in range(11,n+1):
        memo[i]=memo[i-1]+3*memo[i-3]+7*memo[i-10]
    return memo[n]

print(g(1000))
answered Oct 21 by Dong (128 points)
edited Oct 22 by Dong
Let us use just the tabulation answer to keep things simple for other readers.
0 votes
Use this as a hint..

package edu.gwu.cs6212;
import java.math.BigDecimal;

public class Fib {
    public static void main(String[] args) {
        BigDecimal[] fibNums = new BigDecimal[1000];
        fibNums[0] = BigDecimal.ONE;
        fibNums[1] = BigDecimal.ONE;
        for (int i = 2; i < 1000; i++) {
            fibNums[i] = fibNums[i - 1].add(fibNums[i - 2]);
        }
        for (int i = 5; i < 1000; i += 5) {
            System.out.println(i + ": " + fibNums[i - 1]);
        }
    }
}
answered Jun 8 by Amrinder Arora (206 points)
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...