动态规划

2018-03-30

认识论

认识事物的方法概念、判断、推理
推理分为归纳、演绎
- 基本归纳法常常称之为马尔科夫模型，特点是只要状态$A_i$确定，那么计算$A_{i+1}$时不需要考察更新序的状态$A_1…A_{i-1}$的状态。计算机算法中叫做贪心算法。
- 高阶归纳法称之为高阶马尔科夫模型，对于$A_{i+1}$需考察前i个状态集$A_1…A_{i-1}$的状态才可完成整个推理过程。计算机算法中叫做动态规划算法。
- 无后效性对于$A_{i+1}$以后的节点来说，是不会影响到前面的节点的，一旦计算完成，前面的节点不会改变。

贪心算法

动态规划

硬币问题的求解

现有不限数量的面额分别为1元，2元，5元，10元的货币，如果要用这些货币组合成x元，求一共有多少种组合方式？

暴力求解法

从第一个硬币开始，用0个第一个硬币，求解剩余硬币组合成x元的方法，用1个第一个硬币，求解剩余硬币组合成x-1元的方法，……
最终求得结果。

coins = [1, 2, 5, 10]
N = 100
array = []
def solution_digui(price, coin, result):
    if price < 0:
        return
    if price == 0:
        array.append(result)
        return result
    if len(coin) > 0:
        cur = coin[0]
        for i in range(int(N / cur) + 1):
            solution_digui(price - i * cur, coin[1:], result + [cur] * i)
solution_digui(N, coins, [])
print(array)

coins = [1, 2, 5, 10]
N = 100
array = []
def solution_digui(price, coin, result):
    if price < 0:
        return
    if price == 0:
        array.append(result)
        return result
    if len(coin) > 0:
        cur = coin[0]
        for i in range(int(N / cur) + 1):
            solution_digui(price - i * cur, coin[1:], result + [cur] * i)
solution_digui(N, coins, [])
print(array)

记忆搜索法

递归的方法会有大量的重复计算，记忆搜索算法会将结果组成key：value放入到一个map中，进入递归过程前，查询是否存在value，如果存在，则直接取值，这样就减少了递归的次数。