0%

DP

Dynamic programming

算法

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

1
2
3
4
5
6
7
8
9
10
 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 级的台阶总共有多少种跳法。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 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 个整数 T1 <= T <= 1000)和 M1 <= M <= 100),用一个空格隔开,T 代表总共能够用来采药的时间,M 代表山洞里的草药的数目。

接下来的 M 行每行包括两个在 1100 之间(包括 1100)的整数,分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

样例 #1

样例输入 #1
1
2
3
4
 70 3
 71 100
 69 1
 1 2
样例输出 #1
1
 3

提示

【数据范围】

  • 对于 30\% 的数据,M \le 10
  • 对于全部的数据,M \le 100

【题目来源】

NOIP 2005 普及组第三题

WP

背包问题模板:

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

第一个参数含义:

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

第二个参数含义:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 #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]);
 }
-------------本文结束感谢您的阅读-------------
请作者喝一杯蜜雪冰城吧!