江民钦的博客

show me code

算法学习笔记-DP动态规划

动态规划相信大家都知道，动态规划算法也是新手在刚接触算法设计时很苦恼的问题，有时候觉得难以理解，但是真正理解之后，就会觉得动态规划其实并没有想象中那么难。网上也有很多关于讲解动态规划的文章，大多都是叙述概念，讲解原理，让人觉得晦涩难懂，即使一时间看懂了，发现当自己做题的时候又会觉得无所适从。我觉得，理解算法最重要的还是在于练习，只有通过自己练习，才可以更快地提升。话不多说，接下来，下面我就通过一个例子来一步一步讲解动态规划是怎样使用的，只有知道怎样使用，才能更好地理解，而不是一味地对概念和原理进行反复琢磨。

能用动规解决的问题的特点

  • 问题具有最优子结构性质。如果问题的最优解所包含的 子问题的解也是最优的，我们就称该问题具有最优子结 构性质。
  • 无后效性。当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态，没有关系。

    首先，我们来看一道题:

    数值三角形

    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5

在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。 三角形的行数大于1小于等于100，数字为 0 - 99

输入格式：

5      //表示三角形的行数    接下来输入三角形

7

3   8

8   1   0

2   7   4   4

4   5   2   6   5

要求输出最大和

首先看到这道题，由于本人习惯了深度优先搜索的方式去处理问题，所以首先下意识的就想到深度优先搜索。

深度优先搜索代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstring>
using namespace std;
int num[100][100],book[100][100];
int direct[2][2]={{1,0},{1,1}};   //定义方向数组 
int n;
int m=0;   //最大和 
void func(int x,int y){
    if(x>=n){
        int sum=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(book[i][j]!=0){
                    sum+=num[i][j];
                }
            }
        }
        if(sum>m){
            m=sum;
        }
        return;
    }
    for(int i=0;i<2;i++){
        if(book[x][y]==0){
            book[x][y]=1;
            func(x+direct[i][0],y+direct[i][1]);
            book[x][y]=0;
        }   
    }
}
int main(){
    memset(num,0,sizeof(num));
    memset(book,0,sizeof(book));
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<i+1;j++){
            cin>>num[i][j];
        }
    }
    func(0,0);
    cout<<m<<endl;
}

下面看动态规划代码:

动态规划代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
	int n;
	cin>>n;
	int num[n][n];
	for(int i=0;i<n;i++){
		for(int j=0;j<i+1;j++){
			cin>>num[i][j];
		}
	}
	for(int i=n-2;i>=0;i--){
		for(int j=0;j<i+1;j++){
			num[i][j]+=max(num[i+1][j],num[i+1][j+1]);
		}
	}
	cout<<num[0][0];
}

显而易见，动态规划这种方法的时间复杂度明显比深度优先高，所以在考虑此类问题时，为了追求更好的时间复杂度，可以选用动态规划。

动态规划DP算法