总结：动态规划（一）

今天是动态规划的第一讲，从概念的理解上并不难，这是一种分阶段求最优值的算法，将复杂问题按阶段分成子问题，枚举子问题各种可能情况，从中找到最优值（利用子问题最优解，解决问题最优解）在找出子问题后利用递归
与贪心算法的相同点：动态规划和贪心算法都是一种递推算法 。均有局部最优解来推导全局最优解 。
与贪心算法不同：动态规划中全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解边界条件：即最简单的，可以直接得出的局部最优解
主要解决的问题类型：求解最优并且问题可以分为好几个步骤（子问题）问题具有多阶段决策的特征每阶段都有相应的状态与之对应，描述的状态的量称为状态变量每一个阶段都面临一个决策，选最优每一阶段的最优解问题可以递归地归结为下一个阶段各个可能状态的最优解问题各子问题与原问题具有完全相同的结构剧空间顺序或时间顺序对问题的求解划分阶段描述事物的性质，不同事物有不同的性质，因而用不同的状态来刻画，对问题的求解状态的描述是分阶段的对每个阶段做决策用数学公式描述与阶段相关的状态间的演变规律
解题步骤
1.判断问题是否具有最优子结构性质，若不具备则不能用动态规划
2.把问题分成若干个子问题（分阶段）
3.建立状态转移方程
4.找出边界条件
5.将已知边界值带入方程
6.递归求解
例题：
1.吃金币游戏（方格问题）
小明写了一个简单的吃金币游戏，规则:在一个长方形地图上，玩家每次能从一个方格走到相邻一个方格。玩家控制的角色可以向下或者向右走，但不能向上或向左走。每个方格上都有一定的金币。现在，小明想请你帮他想一个策略，尽可能多的获得金币（从左上角走到右下角可能获得的最大金币数）。
思路：
该长方形地图（m*n），规定只能向下或向右走，求从左下角到右下角可能获得的最大金币数
一共走m+n次（向右走m次，向左走n次）
**子问题：**走到第i行，第j列时获得的最大金币数（思考与谁有关），从第i行第j列向前考虑
这种方格问题，遍历所有方格，把每一个方格的最优解求出来（子问题最优解），从而推出整个问题的最优解
F[a][b]表示到(a,b)点时吃到的最大金