菜
Dynamic programming
算法
=记住已经解决过的子问题的解=
1 | A * "1+1+1+1+1+1+1+1 =?" * |
两种形式
①自顶向下备忘录
②自底向上
典型特征
无后效性:未来与过去无关
最优子结构:大问题的最优解可以由小问题的最优解推出
举例-斐波那契数
1.递归方法(复杂度过高)
1 | Fibonacci(n) = 1 ; n = 0 |
但是这样很多重复的节点被执行,每一个子问题的复杂度都是O(1),对应的递归树是一个完全二叉树,有2^n-1个结点,复杂度为O(2^n)。
2.自顶向下备忘录
数组或HashMap充当备忘录。
leetcode原题:一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。
显然就可以得出以下公式:
每一个子问题的复杂度都是O(1),最后递归树变成了树干,复杂度为O(n)。
1 | public class Solution{ |
3.自底向上
台阶数 | 1 | 2 | 3 | 4 | …… | 10 |
---|---|---|---|---|---|---|
子结构 | f(1) | f(2) | f(3) | f(4) | …… | f(10) |
跳法 | 1 | 2 | f(1)+f(2) | f(2)+f(3) | …… | f(8)+f(9) |
temp变量 | a=1 | b=2 | a=1+2=3 | b=2+3=5 | …… | b=a+b |
1 | public class Solution{ |
解题场景与思路
如果一个问题,可以把所有可能的答案穷举出来,并且穷举出来后,发现存在重叠子问题,就可以考虑使用动态规划。比如:
最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等
DP思路:
1.穷举分析(拿纸自己画一画写一写)
2.确定边界(可理解为奠基)
3.找规律,找最优子结构(大问题的最优解可以由小问题的**最优解**推出)
4.状态转移方程
DP原理讨论
DP为什么快
DP自带剪枝,舍弃了很多不可能成为最优解的答案,尽可能缩小可能解的空间,往往把解空间降为多项式级。
DP操作
大事化小,小事化了
DP三连
我是谁? ——设计状态,表示局面
我从哪里来?
我要到哪里去? ——设计转移
练习题1
[NOIP2005 普及组] 采药
题目描述
辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”
如果你是辰辰,你能完成这个任务吗?
输入格式
第一行有 2 个整数 T(1 <= T <= 1000)和 M(1 <= M <= 100),用一个空格隔开,T 代表总共能够用来采药的时间,M 代表山洞里的草药的数目。
接下来的 M 行每行包括两个在 1 到 100 之间(包括 1 和 100)的整数,分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
样例 #1
样例输入 #1
1 | 70 3 |
样例输出 #1
1 | 3 |
提示
【数据范围】
- 对于 30\% 的数据,M \le 10;
- 对于全部的数据,M \le 100。
【题目来源】
NOIP 2005 普及组第三题
WP
背包问题模板:
dp[i]含义:背包容量为i时候的最大价值
第一个参数含义:
我要往背包里装这个物品,背容量减w[j],价值加val[j]
第二个参数含义:
因为容量不够装物品,保持原来的状态dp[i]
1 |
|