Stair steps (Ice Base) - 階段一段飛ばし

どんな問題？

Stair steps
http://www.checkio.org/mission/stair-steps/

各段に数字が書いてあるN段の階段がある。階段の下から上まで、1段または2段（1段飛ばし）ずつ登っていく。このとき、数字の合計が最大になるような登り方を見つけて、その数字の合計値を求めよ。

引数は、階段の各段の数字がリスト形式で渡される。数字は -100＜x＜100 の整数値。階段の下と上は0となる。段数は10以下。
戻り値は、数字の合計の最大値を返す。

例題：

checkio([5, -3, -1, 2]) == 6
checkio([5, 6, -10, -7, 4]) == 8
checkio([-11, 69, 77, -51, 23, 67, 35, 27, -25, 95]) == 393
checkio([-21, -23, -69, -67, 1, 41, 97, 49, 27]) == 125

ヒントに、動的計画法（Dynamic Programming, DP）や、再帰（recursion）を使うと書いてある。

どうやって解く？

動的計画法ってなんだっけ？アルゴリズムの本に載っていた気がするが、すでに返却してしまった。
Wikipediaで調べてみた。

下記2条件を満たすアルゴリズムの総称

1. 分割統治法：部分問題を解き、その結果を利用して、問題全体を解く
2. メモ化：部分問題の計算結果を再利用する

動的計画法 - Wikipedia

なんかよくわからない・・・。

動的計画法はおいといて、普通に全ての組み合わせを試してみればいいんじゃないだろうか。
どうやれば全ての組み合わせを求められるかな？1段ごとに、止まる段かスキップする段かを割り当てて、スキップする段が2個以上連続していれば除外する、という方法でいけるかな。

止まる段は'1'、スキップされる段は'0'として、itertoolsのproductを使って全パターンを求め、結果に'00'が含まれていれば除外する。

for selector in product('01', repeat=len(numbers)):
    if '00' not in ''.join(selector):
        print(selector)

例えば、5段の階段で、indexが2,4の段に止まる場合は、selector='01010' となる。
numbersとselectorから合計値を求めるには、zipを使った。

まとめ

from itertools import product

def checkio(numbers):
    def get_sum_values():
        for selector in product('01', repeat=len(numbers)):
            if '00' not in ''.join(selector):
                yield sum(n for n, s in zip(numbers, selector) if s == '1')

    return max(get_sum_values())

なんか、もっと短くできそうだ。

from itertools import product
checkio = lambda n: max(sum(x for x, c in zip(n, s) if c == '1') for s in product('01', repeat=len(n)) if '00' not in ''.join(s))

http://www.checkio.org/mission/stair-steps/publications/natsuki/python-3/first/

（import行を除けば）One-liner!

他の人の答え

動的計画法（Dynamic Programming）

気になっていた動的計画法だが、タイトルにDynamic Programmingと入っているので、参考にさせてもらった。

def checkio(xs):
    xs.append(0)
    ys = [0, xs[0]]
    for x in xs[1:]:
        ys.append(x+max(ys[-1], ys[-2]))
    return ys[-1]

http://www.checkio.org/mission/stair-steps/publications/H0lyD4wg/python-3/dynamic-programming/

開始から現在までの合計の最大値をysに記録していく。これがメモ化ってことなのかな。最後まで行けば、ysの末尾に答えが入っている。なるほど。

再帰

def checkio(d):
    if len(d) == 0: return 0
    if len(d) == 1: return max(d[0], 0)
    return max(d[0] + checkio(d[1:]), d[1] + checkio(d[2:]))

http://www.checkio.org/mission/stair-steps/publications/Sim0000/python-3/recursive/

こちらは再帰を使った解答。とてもシンプル。

再帰にはどうも苦手意識があって、自分で書こうとすると、いつもどう書けばいいかわからなくなってしまう・・・。