Hi,

First of all, I am new to this place, just finding where to post questions were hard and I am not sure this is the right place for it still. "Start contributing" for "Great problem or idea" is apparently where you get to the discussion part which threw me off but I guess I just need to get to know the platform. I got stuck on the introduction of dynamic programming.

There is a function \(f(N,S)\) that under certain conditions can return \(0\) or \(1\). The final answer is given as \[f(N,S) = \sum_{i=0}^{n-1} f(N-a_m,remove(S,a_m))\].

I may not understand mathematical notation well enough but I was fairly sure that \[\sum_{i=0}^{n-1} expression\] means the sum of \(expression\) where \(i\) will start at \(0\) and go to \(n-1\). Typically \(expression\) would have some reference to \(i\) in it since otherwise you might as well multiply by \(n\). The point is that in the case of the answer \(expression\) is a recursive function evaluation and no other condition or operation outside of it, it can only evaluate to \(0\) which happens when the \(n\) is \(0\) and the sum become a no operation which I assume returns the scalar \(0\) in this case.

How can this function implement the conditions described as the target conditions of the algorithm, like return \(1\) when \(N\) is zero?

Best Regards

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestNote that the correct answer in the referenced question is (A) - \(f(N,S)=\sum _{ i=0 }^{ n-1 } f(N-{ a }_{ i },remove(S,{ a }_{ i }))\) Here the summation index is i, as expected. There seems to be a typo in the explanation to this question. You can report this mistake as explained in this link - reporting a mistake

Log in to reply

I didn't notice that but it still doesn't explain how the function could ever return anything other than 0 (assuming that summation over an empty set is zero).

Log in to reply

Remember that f(0,S)=1 for all S. Thus, if ever f(0, S) is called, the end result will be greater than 0. Therefore, if N-a[i] is ever 0, the end result will be greater than 0. Therefore, if N ever equals a[i], the end result will be greater than 0.

I'm sure you can concieve of a situation in which N can equal a[i], right? Thus, there are ways that the function could return something other than zero. Does that make sense?

Log in to reply

Log in to reply

Like Oded and you pointed out, there had been a typo in the summation indices. This has been fixed now. Do you think this makes more sense now?

Log in to reply

No. The thing I am having problems with is how to know when a condition is part of the problem description or when it is part of the answer. It seems to me that the conditions outlined in the problem description somehow applies even though no such conditions are present in the formula that supposedly is the right answer. What course should I take to get a good understanding of the mathematical notation used?

Log in to reply

What is given to you is \(N\), a number and \(S\), a set of numbers. The question, then, is whether you can pick a subset of elements in \(S\) such that they sum up to \(N\). To understand the explanation, I suggest you go through the example given and work it out yourself. Feel free to ask me related questions that you may have.

Being able to interpret notation is a skill that comes with mathematical maturity. It gets better with a practice of reading mathematical literature like you are doing right now. (So, good job!) In my few years of mathematics studentship, I have come across several pieces of strange notation, and often it stumps me too.

Log in to reply

Log in to reply

Log in to reply