2

I'm trying to learn Dynamic programming but there is some difficult lines of code that are hard to know. Idk what do we suppose to do with these lines of codes:

n, S = map(int, input().split())
w = list(map(int, input().split()))
dp = [0] * (S + 1)
dp[0] = 0
Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
Quân Đoàn
  • 51
  • 1
  • 1
  • 9

1 Answers1

4

This has not much to do with dynamic programming itself.

n, S = map(int, input().split())

will query the user for input, and then split it into words, convert these words in integers, and unpack it into two variables n and S. This thus will succeed when the user enters two numbers (not more, not less).

It works as follows:

  1. input() will query the user for input, and read one line of user input;
  2. .split() will split that input into a list of "words";
  3. map(int, ...) will call int on each word, it will to that lazily (although that is not important here); and
  4. n, S = ... will unpack the expression into two elements, and assign the first one to n and the second one to S.

For example:

>>> n, S = map(int, input().split())
14 25
>>> n
14
>>> S
25

But it will error if you pass only one number, three numbers, etc. like:

>>> n, S = map(int, input().split())
14
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: not enough values to unpack (expected 2, got 1)
>>> n, S = map(int, input().split())
14 25 37
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: too many values to unpack (expected 2)
>>> n, S = map(int, input().split())
foo bar
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: invalid literal for int() with base 10: 'foo'

The line:

w = list(map(int, input().split()))

does more or less the same thing, but instead takes as input from the user a sequence of numbers. There can be zero, one or more numbers. w will store a list of numbers. The list(..) part forces Python to evaluate the map(..) eagerly.

dp = [0] * (S + 1)

Here we will construct a list with S + 1 zeros. In Python, you can multiply a list (and tuple) with an integer n. The result is a list (or tuple) that is n times as large as the original list, and it repeats the elements. For example:

>>> [1,4,2,5] * 3
[1, 4, 2, 5, 1, 4, 2, 5, 1, 4, 2, 5]

Since here the given list contains one zero, it will thus produce a list that contains S+1 zeros.

Finally

dp[0] = 0

will set the first element to zero. But since that was already the case, this line is not very useful.

Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555