动态会计要素有哪些（python算法基础之动态规划）

动态规划（Dynamic programming）

是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

动态规划是一种灵活的方法，不存在一种万能的动态规划算法可以解决各类最优化问题（每种算法都有它的缺陷）。所以除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，用灵活的方法建立数学模型，用创造性的技巧去求解。

基本策略

基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任何问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

动态规划中的子问题往往不是相互独立的（即子问题重叠）。在求解的过程中，许多子问题的解被反复地使用。为了避免重复计算，动态规划算法采用了填表来保存子问题解的方法。

动态规划三要素

整个求解过程可以用一张最优决策表来描述，最优决策表是一张二维表（行：决策阶段，列：问题的状态）表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。

算法实现

例如硬币组合问题，若求凑够11元的最少硬币数，可以先从凑够0元、1元、2元……的子结构开始分析。

from typing import List

amount = 11
coins = [1, 3, 5]

"""
就该问题总结一下，随着要凑够钱数的增加：
1.首先要知道所有不大于该钱数的面值，
2.对于每种面值的硬币，求出当选择一个该面值的硬币时所需的硬币数
当选择一个硬币后，所需硬币数+1，所要凑够的钱数=原所要凑的钱数-该硬币面值，
所要凑够的钱数减少，求减少后要凑钱数最少所需硬币数，属于原问题的子结构，已求出解
3.在上述求出的结果集中，选择最小值，即为要凑够该钱数所需的最少硬币数
"""

def coin_dynamic(money: int, coin_list: List[int]) -> List:
    """ 动态计算 如何用最少的硬币凑够X元；
    :param money: 钱数   int
    :param coin_list: 硬币面值 list
    :return: 
    """
    min_coin_num = [0]

    for i in range(1, money + 1):
        min_coin_num.append(float('inf'))  # 正无穷  sys.maxsize
        for j in range(len(coin_list)):
            if coin_list[j] <= i and min_coin_num[i - coin_list[j]] + 1 < min_coin_num[i]:
                min_coin_num[i] = min_coin_num[i - coin_list[j]] + 1
    return min_coin_num

有n级台阶，一个人每次上一级或者两级，问有多少种走完n级台阶的方法，斐波那契数列！

class Solution:
    """
    @param n: an integer
    @return: an ineger f(n)
    """
 
    def up(self, n):
        L = []
        L.append(1)
        L.append(2)
        for i in range(2, n):
            L.append(L[i - 1] + L[i - 2])
        return L[n - 1]

总结

动态规划：动态规划表面上很难，其实存在很简单的套路：当求解的问题满足以下两个条件时， 就应该使用动态规划：

主问题的答案 包含了 可分解的子问题答案(问题可被递归求解)；递归求解时， 很多子问题的答案会被多次重复利用

动态规划的本质思想就是递归， 但如果直接应用递归方法， 子问题的答案会被重复计算产生浪费， 同时递归更加耗费栈内存， 所以通常用一个二维矩阵（表格）来表示不同子问题的答案， 以实现更加高效的求解。