• 算法
    • 动态规划
      • 基本概念
        • 子问题和原问题
          • 子问题是和原问题具有相似结构但规模比原问题小;如F(10)是求10的阶乘,则F(k)(k<10)就是子问题;
        • 状态
          • 状态就是子问题中变化的量,可以把状态看成我们求解问题的自变量,比如F(10)是求解10的阶乘,自变量10就是一个状态;
        • 状态转移方程
          • 可以表示状态之间转移的方程,一般利用关于状态的某个函数建立起来。例如:阶乘F(n)=n*F(n-1)
        • DP数组
          • 动态规划数组,也就叫做子问题数组,因为DP数组对应一个子问题的结果,DP数组的下标一般是子问题对应的状态。
        • 边界条件
          • 不可在切分子问题的状态,如f(1),求1的阶乘则不可以切分为更小的问题
        • 状态压缩
          • 状态压缩就是用来减少空间复杂度的一个方法,基本思想就是我们在求解问题的时候,一般不用保存全部的DP数组,只保留与求解k状态的状态
      • 条件
        • 能够用动态规划求解问题的条件
          • 满足最优子结构
            • 原问题的最优解包含子问题的最优解
          • 无后效性
            • 在推到后面阶段的状态时,我们只关心前面状态的值,不关心这些值怎么得来的
            • 某阶段的值一旦确定,就不受后面状态的影响
      • 递归
        • 条件
          • 子问题和原问题做同样的事,且子问题更简单
          • 子问题具有最简单的形式,不可再切分,是递归的出口
        • 例子
          • 斐波那契数列
          • 阶乘
        • 优化
          • 自顶向下的缓存
          • 尾递归
          • 自底向上法,也就是动态规划法
      • 求解步骤
        • 定义原问题和子问题
        • 定义状态
        • 定义状态转移方程
        • 用递柜的方法直接求解
        • 用自低线上的方法优化
        • 使用优化状态压缩
      • 经典问题
        • 打家劫舍问题
          • 描述
            • 小偷准备去偷盗,但是街道上装有一个防盗系统,如果相邻两家在同一个晚上被偷的话,防盗系统就会报警,已知街道上的每家的金额数量,问:小偷怎么在一晚上偷盗最多的钱?
          • 解题步骤
            • 定义原问题和子问题
              • 原问题:如何才能从n个房子里偷盗最多的钱?子问题:如何才能从k(k<n)个房子中偷到最多的钱
            • 定义状态
              • 状态k:从前面k个房子偷钱
            • 定义状态转移方程
              • M1; k = 1
              • max(M1, M2); k = 2
              • max(f(n - 1), f(n - 2) + Mk); k > 2
        • 礼物的最大价值
          • 描述
            • 给定m*n(m>0,n>0)棋盘以及单元格内的价值,从左上角开始,只能向右或者向下移动,直到右下角,怎么移动路径经过的单元格总价值最大
        • 零钱兑换问题
          • 描述
            • 给定面值corns = [C1,C2…Ci…,Ct]数组的硬币,求兑换目标金额S最少硬币个数
          • 解题步骤
            • 原问题和子问题
              • 原问题: 求兑换目标金额S需要最少的硬币个数
              • 子问题:求兑换金额x(x <= S)需要最少硬币个数
            • 定义状态
              • f(x):兑换金额x需要的最少硬币个数
            • 状态转移方程
              • 0; x = 0;
              • min(f(x - C1), f(x - C2),… f(x - Ct)) + 1; x > 0
            • 代码
        • 01背包问题
          • 描述
            • 给定背包载重量W,物品重量数组w = [w1,w2,…wn],物品价值数组V = [v1, v2,…vn],问题:背包能装最大价值是多少?
          • 解题步骤
            • 原问题和子问题
              • 原问题
                • 求背包容量为W的背包,从集合为n的物品中挑选,能装的最大价值是多少;
                • 求背包容量为i(i<=W)的背包,从前j件物品中挑选,能装下的最下价值是多少;
            • 定义状态
              • f(i,j)表示容量为i的背包,从前j件物品中挑选,能装下的最大价值,这里的自变量又两位,所以DP数组是二维数组。
            • 状态转移方程
              • 方程
                • f(i, j) =
                  • Max( 前j件商品中重量为1的商品 ); (i = 1, 背包容量为1)
                  • w1 <= i ? v1 : 0; (j = 1, 只有一件物件)
                  • Max(vj + f(i - wj, j - 1), f(i, j - 1)) ;(i > 1; j > 1)
                    • f(i, j-1)表示不要第j件物品的总价值
                    • vj + f(i - wj, j - 1)表示取第j件物品的总价值,其中 i - wj表示剩余背包容量,也就是一个子背包
            • 代码
          • 参考文献