guodong's blog

master@zhejiang university
   

动态规划详解

一:动态规划方法

通常,有两种不同的方法来储存能被反复使用的值,

1、Bottom UP 的tabulation方法。

2、top down的memorization方法。

1、Tabulation Method – Bottom Up Dynamic Programming 

从名字中,我们就能得到,算法先从底部开始计算,具体的状态过程如下:

我们称状态dp[x],初始状态为dp[0],我们的目标状态为dp[n],如果我们从初始状态dp[0]开始计算,最后计算到dp[n]此时我们称为从底到上的结构。

那为什么叫做tabulation方法。使用如下例子

// Tabulated version to find factorial x.
int dp[MAXN];

// base case
int dp[0] = 1;
for (int i = 1; i< =n; i++)
{
    dp[i] = dp[i-1] * i;
}

上面code遵循的就是自底而上的方法,我们可以注意到,dp表被有序的pop,然后我们可以直接获取到所有的计算表,因此我们称为制表法。

2、Memoization Method – Top Down Dynamic Programming 

自定而下的方法和上述相反,只有当我们需要下一个状态时,我们才需要计算下一个状态。

// Memoized version to find factorial x.
// To speed up we store the values
// of calculated states

// initialized to -1
int dp[MAXN]

// return fact x!
int solve(int x)
{
    if (x==0)
        return 1;
    if (dp[x]!=-1)
        return dp[x];
    return (dp[x] = x * solve(x-1));
}

从上面的代码中我们可以看出,我们储存最近的cache,下次我们可以简单的使用return来返回内存的值。

3、两种方法的对比

tabulation-vs-memoization

二:动态规划适用范围

动态规划方法就是将一个复杂的问题分解成子问题,同时储存子问题的结果,并且避免计算重复的过程。以下两种情况,都可以使用动态规划方法:

1、 overlapping subproblems
2、 optimal subproblem

1、overlapping subproblem

在DP中,计算子问题的结果,并将结果储存在table或list中,避免重复计算。所以对于那些不具有相同或者覆盖(overlapping)的子问题来说,DP并不适合。例如,二值查找问题就不具有相同的子问题。

2、Optimal Substructure

例如,最短路径问题,如果节点x位于从源节点u到目标节点v的最短路径上,那么u到v的最短路径就是u到x的最短路径加上x到v的最短路径。

另一方面,最长路径(不考虑循环)就不具有这种最优解关系。

三:如何使用DP算法

使用DP算法的步骤:

1、判断是否适合使用DP算法

2、使用最少的参数来表达一个状态

3、找到状态之间的关系

4、用制表或内存的方法

Step 1 : How to classify a problem as a Dynamic Programming Problem?

1、通常情况下,出现最大,最小的问题,或者有多少种安排的问题

2、DP必须有overlapping的子问题。

Step 2 : Deciding the state

状态的定义:尽量使用较少的参数,描述这个特定的位置或状态。

比如在背包问题中,使用 DP[index][weight]来描述当前状态。

Step 3 : Formulating a relation among the states

这个部分描述各个状态之间的关系,是最难的部分,需要大量的直觉观察和练习。考虑下面一个例子

'''
Given 3 numbers {1, 3, 5}, we need to tell
the total number of ways we can form a number 'N' 
using the sum of the given three numbers.
(allowing repetitions and different arrangements).

Total number of ways to form 6 is: 8
1+1+1+1+1+1
1+1+1+3
1+1+3+1
1+3+1+1
3+1+1+1
3+3
1+5
5+1
'''

首先,我们需要决定每个状态,使用参数n来决定状态,因此,state[n]意味着总共和能为n的所有方法。

How to do it? 

首先是初始化,假设我们已知state (n = 1), state (n = 2), state (n = 3) ……… state (n = 6),我们希望知道state(n=7)的结果,我们有三种方式得到state (n = 7)

1) Adding 1 to all possible combinations of state (n = 6)
Eg : [ (1+1+1+1+1+1) + 1]
[ (1+1+1+3) + 1]
[ (1+1+3+1) + 1]
[ (1+3+1+1) + 1]
[ (3+1+1+1) + 1]
[ (3+3) + 1]
[ (1+5) + 1]
[ (5+1) + 1]

2) Adding 3 to all possible combinations of state (n = 4);

Eg : [(1+1+1+1) + 3]
[(1+3) + 3]
[(3+1) + 3]

3) Adding 5 to all possible combinations of state(n = 2)
Eg : [ (1+1) + 5]

因此结果可以表示成:

state(7) = state (6) + state (4) + state (2)
or
state(7) = state (7-1) + state (7-3) + state (7-5)

也就是说,

state(n) = state(n-1) + state(n-3) + state(n-5)

4. 编写代码,使用两种方式都行

 

参考链接:https://www.geeksforgeeks.org/dynamic-programming/#concepts




上一篇:
下一篇:

头像

guodong

说点什么

avatar
  Subscribe  
提醒