Coin sum dynamic programming in Python

Question

I am preparing for an interview, and here's a popular problem on the dynamic programming. And I want to see if there's any feedback or code review for my solution at dynamic programming question.

#  Problem: Coin Sum
#
#  Given an array of coins and a target total, return how many
#  unique ways there are to use the coins to make up that total.
#
#  Input:  coins {Integer Array}, total {Integer}
#  Output: {Integer}
#
#
#  Example:
#  Input:  [1,2,3], 4
#  Output: 4
#
#  1+1+1+1
#  1+3
#  1+1+2
#  2+2
#
#
#  Input:  [2,5,3,6], 10
#  Output: 5
#
#          2+3+5
#          5+5
#          2+3+2+3
#          2+2+6
#          2+2+3+3
#

#  Note: You have an unlimited number of each coin type. All coins in the
#        coin array will be unique
#        Order does not matter. Ex: One penny and one nickel to create six
#        cents is equivalent to one nickel and one penny
#
#

def coin_sum(coins, total):
    # tabulation way
    arr = [1] + [0] * total
    for coin in coins:
        for i in range(coin, total + 1):
            arr[i] += arr[i - coin]
    return 0 if total == 0 else arr[total]



# Time Complexity: O(N*M), let the number of coins be m.
# We iterate from arr[coin] -> arr[n], or ~ n operations on each coin, hence n*m.
# Auxiliary Space Complexity: O(N)

It passes all of the following 5 tests for my Coin sum tests:

def expect(count, name, test):
    if (count == None or not isinstance(count, list) or len(count) != 2):
        count = [0, 0]
    else:
        count[1] += 1

    result = 'false'
    errMsg = None
    try:
        if test():
            result = ' true'
            count[0] += 1
    except Exception as err:
        errMsg = str(err)

    print('  ' + (str(count[1]) + ')   ') + result + ' : ' + name)
    if errMsg != None:
        print('       ' + errMsg + '\n')

def lists_equal(lst1, lst2):
    if len(lst1) != len(lst2):
        return False
    for i in range(0, len(lst1)):
        if lst1[i] != lst2[i]:
            return False
    return True

print("\nCoin Sum Tests")
test_count = [0, 0]

def test():
    example = coin_sum([1, 2, 3], 4)
    return example == 4

expect(test_count, 'should work for first example case', test)

def test():
    example = coin_sum([2, 5, 3, 6], 10)
    return example == 5

expect(test_count, 'should work for second example case', test)

def test():
    example = coin_sum([2], 10)
    return example == 1

expect(test_count, 'should work for a single coin', test)

def test():
    example = coin_sum([7, 15], 20)
    return example == 0

expect(test_count, 'should work when there is no solution', test)

def test():
    example = coin_sum(
        [78, 10, 4, 22, 44, 31, 60, 62, 95, 37, 28, 11, 17, 67, 33, 3, 65, 9, 26, 52, 25, 69, 41, 57, 93, 70, 96, 5,
         97, 48, 50, 27, 6, 77, 1, 55, 45, 14, 72, 87, 8, 71, 15, 59], 100)
    return example == 3850949

expect(test_count, 'should work for variety of coins and large total', test)

print(('\nPASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1])))

Answer 1

Some tips:

• Know your PEP8, format your code appropriately.
• Learn string formatting - and know the differences between 3.6 and earlier.
• Your errMsg and Exception process seem like you expect an error but what error are you expecting? Might want to specify which error you're expecting from your edge cases. ValueError? AttributeError? Also, you shouldn't perform equality statements against None.
• if (count == None or not isinstance(count, list) or len(count) != 2) has redundant brackets

And use a proper test harness instead of writing your own. Here is your code with your expect function removed and using pytest:

import pytest


def coin_sum(coins, total):
    # tabulation way
    arr = [1] + [0] * total
    for coin in coins:
        for i in range(coin, total + 1):
            arr[i] += arr[i - coin]
    return 0 if total == 0 else arr[total]


def test01():
    example = coin_sum([1, 2, 3], 4)
    assert example == 4


def test02():
    example = coin_sum([2, 5, 3, 6], 10)
    assert example == 5


def test03():
    example = coin_sum([2], 10)
    assert example == 1


def test04():
    example = coin_sum([7, 15], 20)
    assert example == 0


def test05():
    example = coin_sum(
            [78, 10, 4, 22, 44, 31, 60, 62, 95, 37, 28, 11, 17, 67, 33, 3, 65, 9, 26, 52, 25, 69, 41, 57, 93, 70, 96, 5,
             97, 48, 50, 27, 6, 77, 1, 55, 45, 14, 72, 87, 8, 71, 15, 59], 100)
    assert example == 3850949

And here are the results:

C:\PycharmProjects\codereview\tests>pytest test_tt.py
======================== test session starts ========================
platform win32 -- Python 3.7.0, pytest-3.6.2, py-1.5.4, pluggy-0.6.0
rootdir: C:\PycharmProjects\codereview\tests, inifile:
plugins: cov-2.5.1, celery-4.2.0
collected 5 items

test_tt.py .....                                               [100%]

===================== 5 passed in 0.13 seconds ======================

Hope this helps!