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

Question

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

g(n) = g(n-1) + 3 *g(n-3) + 7*g(n-10)

Answer 1

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

Comments

Let us use just the tabulation answer to keep things simple for other readers.

Answer 2

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]);
        }
    }
}