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)f(N,S) that under certain conditions can return 00 or 11. The final answer is given as f(N,S)=i=0n1f(Nam,remove(S,am))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 i=0n1expression\sum_{i=0}^{n-1} expression means the sum of expressionexpression where ii will start at 00 and go to n1n-1. Typically expressionexpression would have some reference to ii in it since otherwise you might as well multiply by nn. The point is that in the case of the answer expressionexpression is a recursive function evaluation and no other condition or operation outside of it, it can only evaluate to 00 which happens when the nn is 00 and the sum become a no operation which I assume returns the scalar 00 in this case.

How can this function implement the conditions described as the target conditions of the algorithm, like return 11 when NN is zero?

Best Regards

Note by Mikael Lövqvist
7 months, 2 weeks ago

No vote yet
1 vote

  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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. 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"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Note that the correct answer in the referenced question is (A) - f(N,S)=i=0n1f(Nai,remove(S,ai))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 - 7 months, 2 weeks ago

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

Mikael Lövqvist - 7 months, 2 weeks ago

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?

Adrian Self - 7 months, 2 weeks ago

Log in to reply

@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?

Mikael Lövqvist - 7 months, 2 weeks ago

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?

Agnishom Chattopadhyay Staff - 6 months, 2 weeks ago

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?

Mikael Lövqvist - 6 months, 2 weeks ago

Log in to reply

What is given to you is NN, a number and SS, a set of numbers. The question, then, is whether you can pick a subset of elements in SS such that they sum up to NN. 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 Staff - 6 months, 2 weeks ago

Log in to reply

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

Mikael Lövqvist - 6 months, 2 weeks ago

Log in to reply

@Mikael Lövqvist I am sorry, I believe you misunderstood my comment. The format of the expression is by no means a guessing game. The function ff can indeed be rigorously defined through mathematical notation, or via means of a programming language if necessary.

Agnishom Chattopadhyay Staff - 6 months, 2 weeks ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...