Python list dimension size error

Question

Consider the following code in python:

def main():
    n = input( )
    s = input( )

    coins = [ 0 ]*n
    dp = [ 0 ]*( s+1 )

    print coins
    print dp

    for i in range( n ) :
        coins[ i ] = input( )

    dp[ 0 ]=0
    dp[ 1 ]=1

    for i in range( 2, s+1 ) :
        min_val = 999999
        for j in range( 0, n ) :
            if i-coins[ j ] > 0 :
                if dp[ i-coins[ j ] ] + 1 < min_val :
                    min_val = dp[ i-coins[ j ] ] + 1


    print coins
    print dp

    print coins[ s ]

if __name__ == "__main__" :
    main()

When I compile and run this program, I get the following runtime error:

File "test.py", line 33, in <module>
  main();
File "test.py", line 30 in main
  if dp[ i-coins[ j ] ] + 1 < min_val :

IndexError: list index out of range

What's wrong with it?

Input:

5 10
1 3 5 7 9

You do not need to use ; semicolons in python. They only add noise. — Martijn Pieters
– Martijn Pieters, Commented Sep 21, 2012 at 15:35
Given that you've already used the expression coins[j] in the line above, that can't be it. Try printing the value of that expression. — Fred Foo
– Fred Foo, Commented Sep 21, 2012 at 15:37
Why are you importing array? You're not using any of the functions in that module. — Daniel Roseman
– Daniel Roseman, Commented Sep 21, 2012 at 15:39
@MartijnPieters I write basically in C++, so I have got used to add ; — Rontogiannis Aristofanis
– Rontogiannis Aristofanis, Commented Sep 21, 2012 at 15:40
I think you got confused about arrays as well then. In your code you are using python lists, which is fine, but don't call them arrays, nor do you need to import the array module. — Martijn Pieters
– Martijn Pieters, Commented Sep 21, 2012 at 15:42

Marcus · Accepted Answer · 2012-09-21 15:54:44Z

1

try to use

coins = [ 0 ]*n
dp = [ 0 ]*( s+1 )

to init the array.

I got an total different error on my machine:

  File "ttt.py", line 31, in <module>
    main()
  File "ttt.py", line 21, in main
    if dp[ i-coins[ j ] ] + 1 < min_val :
TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'

and print dp[s] rather than print coins[s] at the last line.

edited Sep 21, 2012 at 15:54

answered Sep 21, 2012 at 15:48

Marcus

6,8794 gold badges22 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

ecatmur · Accepted Answer · 2012-09-21 15:38:12Z

1

We know (from the previous line if) that i-coins[ j ] > 0, so it must be greater than or equal to len(dp), which is s + 1. i is less than s+1, so coins[ j ] is a negative number.

Did you enter a negative number for one of the coins?

answered Sep 21, 2012 at 15:38

ecatmur

158k28 gold badges311 silver badges387 bronze badges

Comments

fatrock92 · Accepted Answer · 2012-09-21 15:47:59Z

0

dp is s+1 length but your for loop goes to n. If s+1 > n then this would work. But in this case I think your s+1 < n.

dp = [ None ]*( s+1 ); # dp is s+1 in length.

for j in range( 0, n ) # loop goes to n.

list index out of range means that s+1 < n

edited Sep 21, 2012 at 15:47

answered Sep 21, 2012 at 15:37

fatrock92

8371 gold badge8 silver badges16 bronze badges

Collectives™ on Stack Overflow

Python list dimension size error

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related