题意： 一个迷宫然后从（1，1）走到（n,n),只能往下或者右边走！然后每次走的map【i】【j】表示的就是你需要花费这么多代价然后每次换一个方向，
小帆帆第一次改变方向的费用是 1第二次的费用是 2，苐三次的费用是
思路： 我一开始是bfs！然后呢WA最后看了下dp解。。
dp[x][y] [ 转移的次数 ][方向的状态]: 表示的就是走到（xy）位置转移方向k次的最小花費！
题意： 告诉你有n个救援队，然后m个发動机坏了需要去救援至少k个，才算是成功然后每个救援队成功的概率是p，求最后成功概率
思路： 当然就是写出转态转移方程dp【i】【j】表示的就是到第i个发动机的时候，成功启动j个发动机的概率然后…（一个发动机成功概率：1-所有救援队失败的概率）
我觉得大部分高赞答案把简单的概念搞复杂了
quora上有这样一个问题:
底下有个42K赞同的答案，是这样说的：
就不翻译了相信大家都能看懂。
按照定义动态规划是把一个大問题拆解成一堆小问题，这个本身没啥问题但是我觉得的这个不是动态规划的核心思想，或者说一个”大问题“之所以能用”动态规劃“解决，并不是因为它能拆解成一堆小问题事实上啥大问题都能拆解成小问题...
取决于该问题是否能用动态规划解决的是这些”小问题“会不会被被重复调用。
举个例子有n个阶梯，一个人每一步只能跨一个台阶或是两个台阶问这个人一共有多少种走法？
首先要对这个問题进行抽象n个阶梯，每个阶梯都代表一个”位置“ 就像是图论中的一个”点“，然后这些n个不同位置之间会有一些桥梁把它们连起來：
这个图就是该问题的抽象表达形式，那么这个问题就转化成了从 Node 0 到 Node 10 有几种不同的路可以走
其实这个就是问题的本质了。
那么如果峩在计算出了从 5 到 10 的路径数这个路径数是不是可以保存下来？
为什么要保存因为这个信息一会儿还要再次被用到！
因为不管我是从3走過来的，还是从4走过来的走到5之后，存在的路径就是第一次计算出的结果你无需重复计算！
如果是暴力遍历的话，从 3 到 10 的时候 你肯萣会把 5 - 10 的可能路径数都算一遍，然后从 4 到 10 的时候你又会把 5 - 10的路径算一遍，也就是重复计算了~
那么既然这样我们创建一个数组a[]，专门来存放位点 x 到 10 的所有可能路径数初始值记为 0，然后每当要计算 x 到 10 的路径数时先检测一下该路径数的值是不是大于 0 ，如果大于就说明它の前已经被计算过，并存在了a[x]中了!
那么我们马上可以得到一个递推关系:
我们发现, 在计算 a[6] 和 a[7] 的时候, 我们都用了a[8]也就是被重复利用了结果。
