菜

Dynamic programming

算法

=记住已经解决过的子问题的解=

 A * "1+1+1+1+1+1+1+1 =？" *
 
 A : "上面等式的值是多少"
 B : *计算* "8!"
 
 A *在上面等式的左边写上 "1+" *
 A : "此时等式的值为多少"
 B : *quickly* "9!"
 A : "你怎么这么快就知道答案了"
 B : "只要在8的基础上加1就行了"

两种形式

①自顶向下备忘录

②自底向上

典型特征

无后效性：未来与过去无关

最优子结构：大问题的最优解可以由小问题的最优解推出

举例-斐波那契数

1.递归方法（复杂度过高）

1
2
3

 Fibonacci(n) = 1 ; n = 0
 Fibonacci(n) = 1 ; n = 1
 Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)

但是这样很多重复的节点被执行，每一个子问题的复杂度都是O(1),对应的递归树是一个完全二叉树，有2^n-1个结点，复杂度为O(2^n)。

2.自顶向下备忘录

数组或HashMap充当备忘录。

leetcode原题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。

显然就可以得出以下公式:

$f(n) = f(n-1)+f(n-2) \\ f(n):跳到n的跳法数量$

每一个子问题的复杂度都是O(1),最后递归树变成了树干，复杂度为O(n)。

 public class Solution{
 	Map<Integer,Integer> tempMap = new HashMap();
 	public int numWays(int n){
 	if(n==0)
 	{
 		return 1 ;
 	}
 	if(n<=2)
 	{
 		return 1 ;
	 }
 	if(tempMap.containsKey(n)){
 		return tempMap.get(n);
 	}else{
 		tempMap.put(n,(numWays(n-1)+numWays(n-2)))
 	return tempMap.get(n);
 	}

 	}
 }

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

 public class Solution{
 	public int numWays(int n){
 		if(n<=1){
 			return 1 ;
		 }
 		if(n==2){
 			return 2 ;
 		}
 		int a = 1 , b = 2 , temp = 0;
 		for(int i=3;i<=n;i++){
 			temp = a + b ;
			 a = b ;
			 b = temp ;
 		}
 		return temp ;
 	}
 }

解题场景与思路

如果一个问题，可以把所有可能的答案穷举出来，并且穷举出来后，发现存在重叠子问题，就可以考虑使用动态规划。比如：

最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等

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

提示

【数据范围】

对于 30\% 的数据，M \le 10；
对于全部的数据，M \le 100。

【题目来源】

NOIP 2005 普及组第三题

WP

背包问题模板：

$dp[i]=max(dp[i-w[j]]+val[j],dp[i])$

dp[i]含义：背包容量为i时候的最大价值

第一个参数含义：

我要往背包里装这个物品，背容量减w[j]，价值加val[j]

第二个参数含义：

因为容量不够装物品，保持原来的状态dp[i]

 #include<stdio.h>
 int w[105] , val[105] ;
 int dp[1005] ;
 
 int max(int a , int b){
     if(a>=b) return a ;
     return b ;
 }
 
 int main()
 {
     int t, m ;
     scanf("%d %d",&t,&m) ;
     for(int i=1;i<=m;i++)
     {
         scanf("%d%d",&w[i],&val[i]);
     }
     for(int i=1;i<=m;i++) 
     {
         for(int j=t;j>=0;j--) 
         {
             if(j>=w[i])
             {
                 dp[j]=max(dp[j-w[i]]+val[i], dp[j]);
             }
         }
     }    
     printf("%d",dp[t]);
 }