Python3でAt CoderのTypical DP Contestに挑戦してみる（その１ Aコンテスト）

Typcal DP Contest A コンテスト

最近pythonの勉強を始めた。
最初にPaizaのPaizaラーニングPython3入門編をやり，
そのあとで「AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～」をやった。
次に何をしようかと思い，同じくAt CoderのTypical DP Contestをやってみることにした。

DPにと言われる分野（？）についてほぼ知らなかったので，いろいろ調べながら書いた（というか真似ただけ）
参考にしたサイトは以下
-プログラミングコンテストでの動的計画法
-クリエイティヴなヴログ

一つめのプログラミングコンテストでの動的計画法というスライドでDPの初歩の何たるかのイメージをつかみ（今回のような問題をナップサック問題と呼ぶらしい。ナップサック問題の特殊な形で少し簡単にしてある），クリエイティヴなヴログで今回の問題について真似してpythonで書いてみたという感じ。
ほうほうなるほどなるほど，と感銘を受けながらやっとサンプルの入力も通ったのでいざ提出したらTLEでした。
もう少し考えます。

[2018/10/06]
コメントをいただいて，修正しました。
大きな変更点は，doneというlistに計算可能ならTrue，そうでないならFalseを格納して，条件分岐をしていたのですが，それだとすでに計算している値に対して再度計算を実行してしまっていたので，doneの各要素を-1で初期化して，値が-1なら計算可能かどうか調べる(can_make内の処理）TrueまたはFalseであればその値をそそまま返すという形にしました。

また，pythonのことをよくわかっておらずお恥ずかしい書き方をしていた個所も指摘いただいたので，修正しました。

ソースコードの主な変更，追記個所は以下

    #can_makeの最初に処理を追加（計算済みかどうか調べる）
    if done[ind][val] != -1:
        return done[ind][val]

#計算可能かどうか（-1で初期化。-1のときはまだ計算していない）
done = [[-1 for i in range(total+1)] for j in range(n+1)]

修正したソースコード（全文）

tdpc_a.py

#ind番目までのコンテストで，合計得点がvalとなるかどうか
def can_make(ind, val):

    #すでに計算済みであれば計算可能かどうかを返却
    if done[ind][val] != -1:
        return done[ind][val]

    #以下は，計算をまだ実行していないときの処理（done == -1のとき）

    if ind == 0:#一つも問題を解かない場合
        return val==0#valが0であればTrue，そうでなければFalseを返却

    #ind-1番目まででvalまたは，val-p[ind-1]が作れたらOK
    if val - p[ind-1] < 0:#val - p[ind-1] < 0のときはvalが作れるかどうかだけ調べる
        if can_make(ind-1,val):
            done[ind][val] = True#計算済みにして，Trueを返却
            return True
        else:
            done[ind][val] = False
            return False

    else:
        if can_make(ind-1,val) or can_make(ind-1,val-p[ind-1]):
            done[ind][val] = True
            return True
        else:
            done[ind][val] = False
            return False


"""
ここからmain
"""

#コンテストの数
n = int(input())

#入力により与えられる各コンテストの得点
p = list(map(int,input().split()))

#得られる得点の最大値をtotalに格納（この値までをすべてcan_makeで調べる）
total = sum(p)

#計算可能かどうか（-1で初期化。-1のときはまだ計算していない）
done = [[-1 for i in range(total+1)] for j in range(n+1)]

#作れる値が何個あるか
cnt = 0
cnt = sum(1 for i in range(total+1) if can_make(n,i))

print(cnt)