Trouble understanding dynamic programming explanation

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

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 2

paragraph 1

paragraph 2

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

example link

> This is a quote

This is a quote

    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"

# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"

Math

Appears as

Remember to wrap math in $ ... $ or \[ ... \] to ensure proper formatting.

2 \times 3

2 \times 3

2^{34}

2^{34}

a_{i-1}

a_{i-1}

\frac{2}{3}

\frac{2}{3}

\sqrt{2}

\sqrt{2}

\sum_{i=1}^3

\sum_{i=1}^3

\sin \theta

\sin \theta

\boxed{123}

\boxed{123}

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

Note 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

Oded Barash - 2 years, 4 months ago

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

A Former Brilliant Member - 2 years, 4 months ago

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?

Adrian Self - 2 years, 4 months ago

@Adrian Self – I don't understand how f(0,S) can ever evaluate to 1 unless there are implicit rules that are outside of the answer. I thought the answer would be explicit in nature. If this is not the case, how can I know when the answer is including these previously mentioned conditions as implicit rules and when the answer should accommodate for those conditions by embedded conditions in the formula?

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?

Agnishom Chattopadhyay - 2 years, 3 months ago

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?

A Former Brilliant Member - 2 years, 3 months ago

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.

@Agnishom Chattopadhyay – I never expected the format of this place to be a guessing game, especially not "dynamic programming" considering that traditional programming often is very strictly defined in its syntax and definitions of various concepts and behaviors. The thing I didn't understand that I have a guess about now is that the function has different definitions based on conditions, the function is not defining the conditions as you typically would do in a programmatic function.

@A Former Brilliant Member – I am sorry, I believe you misunderstood my comment. The format of the expression is by no means a guessing game. The function $f$ can indeed be rigorously defined through mathematical notation, or via means of a programming language if necessary.

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$