Variant 17.1.2 Write a program that takes final score and scores for individual plays and returns the number of sequences of plays that return in the final score

#1

Hi,

Can anybody give me hint how to approach that? Thanks

0 Likes
#2

I struggled with dynamic programming myself. I didn’t start to get the hang of it till I’d done about a dozen problems in the book.

What began to make a difference for me was getting in the habit of always first finding and implementing a purely recursive solution. Then I investigate that solution to see how and where function parameters and results are being repeated i.e. where there are redundant calls, and the presence of patterns in the calls. Put trace statements in to print parameters and return values. It’s those repeats that a dynamic programming solution attempts to optimize out of the recursive solution. They’ll also give you an idea of how to translate a recursive top-down solution to a bottom-up dynamic one.

After going through this initial step this a number of times, you may start to find that you’re able to skip directly to a dynamic programming solution without it.

0 Likes
#3

Thanks for reply, I was able to write recursive solution but I’m unable to map it to DP:

template<typename T>
int getAllComb(std::vector<T> const& input, int sum, int currSum = 0) {
    if (sum == currSum) {
        return 1;
    } else if (currSum > sum) {
        return 0;
    }
    int howMany = 0;
    for (int i = 0; i < input.size(); ++i) {
        int prev = 0;
        prev = getAllComb(input, sum, currSum + input[i]);
        if (!prev && ((i + 1 == input.size()) || (currSum + input[i+1] > sum))) {
            return howMany;
        }else {
            howMany += prev;
        }
    }
    return howMany;
}

Basically I optimized it to cut off the unnecessary calls if sum is already to high, but I’m stuck here. Any hints?

Thanks,

0 Likes
#4

Instead of passing both sum and currSum + input[i] as parameters, is it possible to achieve the same result as the current recursive solution, but by calling the function with a smaller sum each time?

What you currently have is a recursive solution that already has some of the “building up” type behavior that a dynamic solution would have. Specifically, the parameter currSum starts at 0 and builds up to sum.

Let’s delay on the “building up” part till we get to the dynamic solution, and for now just have the recursive solution try to break the problem into recursive calls that operate on “smaller” problems.

0 Likes
#5

Thanks for reply,

I don’t know if this is what you meant by smaller problems, but I noticed that I tried the same remaining sum checking which should be hashed, so my recursion looks like this:

std::map<int, int> visited;

template<typename T>
T getAllComb(std::vector<T> const& input, T sum) {
    if (!sum) {
        return 1;
    } else if (sum < 0) {
        return 0;
    }
 
    T howMany = 0;
    for (int i = 0; i < input.size(); ++i) {
        if (visited.count(sum - input[i])) {
            ++visited[sum - input[i]];
            howMany += visited[sum - input[i]];
            continue;
        }
        std::cout << "Going deeper with checking " << sum - input[i] << std::endl;
        T prev = getAllComb(input, sum - input[i]);
        if (prev > visited[sum - input[i]]) {
            visited[sum - input[i]] = prev;
        }
    }
    return howMany;
}

I think I can see that It do not have to be recursion now.

0 Likes
#6

Great. And I see you have caching now too. I think all you have left is to see how it might be possible to achieve the same result by inverting the recursive “top-down” approach i.e. turning it into the dynamic programming “bottom-up” approach.

0 Likes
#7

Yes, I can see that now.
Here is DP solution:

template<typename T>
T howManyDP(std::vector<T> const& input, T sum) {
    std::map<int, int> cache;
    cache[0] = 1;
    std::find(input.begin(), input.end(), 1) != input.end() ? cache[1] = 1 : cache[1] = 0;


    for (int i=0; i <= sum; ++i) {
        for (int j = 0; j < input.size(); ++j) {
            if (cache.count(i - input[j])) {
                cache[i] += cache[i - input[j]];
            }
        }
    }
    return cache[sum];
}

The lesson learned for me is “don’t count something you already counted”. But this is very simple sentence. In this specific problem we have to provide combinations i.e : for input {2,3,4} and sum 7, after we counted that combination {2, 3, 2} sums to:
2
2 + 3
2 + 3 + 2
and it leads to solution, all those sums when encountered again should be treated as another solution. And is’t indeed true if just think that some of numbers {a1, …, an} summing to S, no matter in which order.

Thanks!

0 Likes
#8

:smile: You got it. Well done!

0 Likes