设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

动态规划(新手入门)

导读:                 动态规划是是非常重要的,我们平常遇到的很多问题都可以用动态规划来解答。解决这类问题可以很大地提升你的能力与技巧。       什么是动态规划?        先对动态规划做一个大致的了解,动态规划算法通常基于一个递推公式及一个或多个初始状态。 当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度。分治法是通过将问题分划分为独立的子问题,...。。。

         

        动态规划是是非常重要的,我们平常遇到的很多问题都可以用动态规划来解答。解决这类问题可以很大地提升你的能力与技巧。


       什么是动态规划?


        先对动态规划做一个大致的了解,动态规划算法通常基于一个递推公式及一个或多个初始状态。 当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度。分治法是通过将问题分划分为独立的子问题,递归的求解子问题,然后合并子问题的解得到原问题的解。动态规划适用于子问题不是独立的情况。各个子问题中包含公共的子问题,这种情况下,递归求解子问题会做多不必要的工作:重复的求解子问题的解。先来看一个题目来感受下


       题目1:


        有一个数字三角形,从三角形的顶部到底部有很多条不同的路径,对于每条路径,把路径上的数加起来可以得到一个和,和最大的路径成为最佳路径。任务是求出最佳路径的数字之和。路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。

        

        该题目也是POJ上的一个题目:猛戳我


       

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

        我们用D(r,j)来表示第r行第j个数字,MaxLength(r,j)表示从r行的第j个数字到底边的最佳路径的值。则我们需要求出来MaxLength(1,1)

        从D(r,j)出发只能走D(r+1,j)或者D(r+1,j+1),那么如何确定MaxLength(r,j)的最佳路径,只需要找到MaxLength(r+1,j)和MaxLength(r+1,j+1)的最大值就可以了。 这个我们可以很轻易的写出一个递归程序。

        递归代码:

////  MaxSum.cpp//  MaxSum////  Created by chenhao on 12/17/13.//  Copyright (c) 2013 mini. All rights reserved.//#include using namespace std;const int MAX_SIZE = 100;int data[ MAX_SIZE + 10 ][ MAX_SIZE + 10 ];int N;int MaxSum( int r, int j ){    if( r == N )        return data[ r ][ j ];    int sum1 = MaxSum( r + 1, j );    int sum2 = MaxSum( r + 1, j + 1 );    if( sum1 > sum2 )        return sum1 + data[ r ][ j ];    else        return sum2 + data[ r ][ j ];}int main(int argc, const char * argv[]){    cin >> N;    for( int i = 1; i <= N; i++ ){        for( int j = 1; j <= i; j++ ){            cin >> data[ i ][ j ];        }    }    cout << MaxSum( 1, 1 ) << endl;       return 0;}

         代码简洁,但是效率非常低。因为产生了过多的重复计算。因为我们计算MaxSum(r,j) 需要去计算MaxSum(r+1,j+1),而去计算MaxSum(r,j+1),同样会去计算MaxSum(r+1,j+1),造成了重复计算。因为这个是函数调用来计算的,当递归调用的层级很多的时候,会造成内存问题,也会造成很糟糕的效率问题。


       我们可以把每个MaxSum(r,j)要计算的次数打印出来,看看到底每个函数调用了多少次。代码:

#include using namespace std;const int MAX_SIZE = 100;int data[ MAX_SIZE + 10 ][ MAX_SIZE + 10 ];int num[ MAX_SIZE + 10 ][ MAX_SIZE + 10 ];int N;int MaxSum( int r, int j ){    num[ r ][ j ]++;    if( r == N )        return data[ r ][ j ];    int sum1 = MaxSum( r + 1, j );    int sum2 = MaxSum( r + 1, j + 1 );    if( sum1 > sum2 )        return sum1 + data[ r ][ j ];    else        return sum2 + data[ r ][ j ];    }int main(int argc, const char * argv[]){    cin >> N;    for( int i = 1; i <= N; i++ ){        for( int j = 1; j <= i; j++ ){            cin >> data[ i ][ j ];        }    }    memset(num, 0, sizeof(num));    cout << MaxSum( 1, 1 ) << endl;    for( int i = 1; i <= N; i++ ){        for( int j = 1; j <= i; j++ ){            cout << num[ i ][ j ] << " ";        }        cout << endl;    }    return 0;}

        执行:
573 88 1 0 2 7 4 44 5 2 6 5301 1 1 1 2 1 1 3 3 1 1 4 6 4 1 

        可以看出来,当N仅仅等于5的时候,最后一行的计算总次数是16.当N变得很大的时候,总的计算次数将会变得非常恐怖,因此我们需要找一个更犀利的算法来代替递归算法。


       问题出在重复计算,所以我们可以轻易的找到解决方法,计算出来MaxSum(r,j)的时候就将其保存下来,下次在用到的时候就直接调用,不需要再重复计算了。每个MaxSum(r,j)都只需要计算一次。

       如果保存MaxSum(r,j)的值呢,这个比较简单,用一个二维数组就可以了,初始值设置为-1,如果计算出来就更新,调用MaxSum(r,j)的时候先判断数组这个值是否为-1,如果不是,则直接返回该值。

       代码:

Source CodeProblem: 1163  User: m68300981Memory: 352K  Time: 32MSLanguage: C++  Result: AcceptedSource Code#include using namespace std;const int MAX_SIZE = 100;int dp[ MAX_SIZE + 10 ][ MAX_SIZE + 10 ];int data[ MAX_SIZE + 10 ][ MAX_SIZE + 10 ];int N;int Max( int & x, int & y ){    return ( x > y) ? x : y;}int CalculateLongNum( int row, int column ){    if ( row == N )        return data[ row ][ column ];    if ( dp[ row + 1 ][ column ]  == -1 )        dp[ row + 1][ column ] = CalculateLongNum(row + 1, column );    if( dp[ row + 1][ column + 1 ] == - 1 )        dp[ row + 1][ column + 1 ] = CalculateLongNum(row + 1, column + 1 );    if( dp[ row + 1 ][ column + 1 ] > dp[ row + 1][ column ] )        return dp[ row + 1 ][ column + 1 ] + data[ row  ][ column ];    else        return dp[ row + 1 ][ column ] + data[ row ][ column ];    }int main(int argc, const char * argv[]){    cin >> N;    for( int i = 1; i <= N; i++ ){        for( int j = 1; j <= i; j++ ){            cin >> data[ i ][ j ];        }    }    memset( dp, -1, sizeof(dp));    cout << CalculateLongNum( 1, 1 ) << endl;        return 0;}

             实际上我们这样做还是递归算法,只不过是我们对递归算法进行了优化,不过我们已经用到了动态规划的思想。


        将一个问题分解为子问题进行递归求解,并且将中间结果保存以避免重复计算的办法,叫做动态规划。一般用于求最优解。对于动态规划的题目,我们一般都会有一个状态转移方程。上文中MaxSum(r,j)表示第i行第j列的那个元素的最佳路径。我们将它定义为该问题的"状态", 这个状态是怎么找出来的呢?我们可以根据子问题定义状态。你找到子问题,状态也就浮出水面了。 最终我们要求解的问题,可以用这个状态来表示:MaxSum(1,1), 那状态转移方程是什么呢?既然我们用MaxSum(r,j)表示状态,那么状态转移方程自然包含MaxSum(r,j), 上文中包含状态MaxSum(r,j)的方程是:MaxSum(r,j) = max(MaxSum(r+1,j),MaxSum(r+1,j+1))+data[r][j]。没错, 它就是状态转移方程,描述状态之间是如何转移的。有了状态转移方程,代码就变得简单了。当然Talk is cheap,show me the code。


        Code:

Source CodeProblem: 1163  User: m68300981Memory: 352K  Time: 32MSLanguage: C++  Result: AcceptedSource Code#include using namespace std;const int MAX_SIZE = 100;int MaxSum[ MAX_SIZE + 10 ][ MAX_SIZE + 10 ];//MaxSum 记录最长路径值int data[ MAX_SIZE + 10 ][ MAX_SIZE + 10 ];int N;int main(int argc, const char * argv[]){    cin >> N;    for( int i = 1; i <= N; i++ ){        for( int j = 1; j <= i; j++ ){            cin >> data[ i ][ j ];        }    }    for( int j = 1;  j <= N; j++ )        MaxSum[N][j] = data[N][j];        //由状态转移方程,从下到上求MaxSum[r][j]    for( int i = N - 1; i > 0; i-- ){        for( int j = 1; j <= i; j ++ ){            if( MaxSum[ i + 1][ j + 1] > MaxSum[ i + 1][ j ] )                MaxSum[ i ][ j ] = MaxSum[ i + 1 ][ j + 1 ] + data[ i ][ j ];            else                MaxSum[ i ][ j ] = MaxSum[ i + 1][ j ] + data[ i ][ j ];        }    }        cout <<  MaxSum[ 1 ][ 1 ] << endl;}


       写到这里我们对动态规划有一个简单的了解了,许多求最优解的问题可以用动态规划来解决。先将原问题分成若干个子问题,然后根据子问题的最优解来求得原问题的最优解。与递归的区别就在于,递归需要导致子问题重复计算,而动态规划的做法是子问题一旦被解出来就会保存起来,所以子问题在动态规划的解法中只解了一次。


        状态和状态转移方程:

        状态是和子问题相关的各个变量的一组取值,一个状态一般对应一个或者多个子问题。所谓状态的值,就是状态对应子问题下面的解。例如上题(r,j)到底边路径的最大和,涉及到两个变量r和j,则一个状态就是对r和j的一组取值。也就是说每个位置就是一个状态。该状态对应的值,就是子问题的解。

        状态转移方程:定义了状态之后,找出不同状态之间是如何迁移的,如何从已知解的状态中,求出另外一个没有值的状态,一般可以用一个递归公式 来表示,此公式就称作状态转移方程。


      题目2:


        OK,我们做完了题目1,初步了解了动态规划的思想,在来做一个动态规划中的入门经典题目,最长非降子序列问题。

        题目:一个序列有N个数:A[1],A[2],…,A[N],求出最长非降子序列的长度。 (讲DP基本都会讲到的一个问题LIS:longest increasing subsequence)

        思想:

        面对这样一个问题,我们应该首先把问题分解成一个子问题,并且定义一个“状态”来代表它的子问题, 并且找到它的解。注意,大部分情况下,某个状态只与它前面出现的状态有关, 而独立于后面的状态。经过分析,我们可以让"求以A[k](k = 1,2,3。。 N)为终点的最长非降子序列的长度“作为一个子问题。这里把最长非降子序列的最右边的数作为子序列的重点,虽然子问题和原问题本身并不一样(并不要求最后边的点是终点),但是我们只要N个子问题都解决掉,那么其中最大的就是原问题的解。

        让我们来一步步找到“状态”和“状态转移方程”,子问题我们已经选好了,"求以A[k](k = 1,2,3。。 N)为终点的最长非降子序列的长度"。假设我们设置状态为MaxLen(k),表示以A[k]作为"终点"的最长非降子序列的长度。可以推出来做状态转移方程。
 
        如何找到状态方程,我们对着实例来分析一下,假设序列为:
1 7 3 5 9 4 8

        根据上文我们找到的状态,可以得知:
  • MaxLen(1) 为1 (序列为1)
  • MaxLen(2) 为2 (序列为1,7   因为MaxLen(1)的最后一个值小于7,则以7 结尾的MaxLen(2) 等于MaxLen(1) + 1        )
  • MaxLen ( 3) 为2 (序列为 1,3  序列以3为结尾,1小于3,7大于3,则MaxLen(3) = MaxLen(1)+1    )
  • MaxLen(4) 为3 (序列为1,3,5  MaxLen(4) = max{ MaxLen(1),MaxLen(3)} + 1           )
  • MaxLen(5) 为4 (序列为1,3,5,9 MaxLen(5) = max{ MaxLen(1),MaxLen(2),MaxLen(3),MaxLen(4)} + 1       )
  • MaxLen(6) 为3 (序列为1,3,4     )
  • MaxLen(7) 为5 (序列为1,3,5,8 )
        则可以得出最大值为4,  在Max(i){ 1<=i <=N)中取最大值。分析到这,状态转移方程已经很明显了
        
MaxLen(k) = Max{ MaxLen(i): 1        Talk is Cheap,show me the Code:

////  MaxSum.cpp//  MaxSum////  Created by chenhao on 12/17/13.//  Copyright (c) 2013 mini. All rights reserved.//#include using namespace std;const int MAX_SIZE =  100;int data[ MAX_SIZE + 10 ];int MaxLen[ MAX_SIZE + 10 ];int N;int main(int argc, const char * argv[]){    while( cin >> N ){        for( int i = 1; i <= N; i++ )            cin >> data[ i ];        MaxLen[ 1 ] = 1;        //由状态转移方程,从1到N求MaxLen(k)状态        for( int i = 2; i <= N; i++ ){            int recordMaxLen = 0;            for ( int j = 1; j < i; j++ ){                if( data[ j ] < data[ i ] ){                    if( recordMaxLen < MaxLen[ j ] )                        recordMaxLen = MaxLen[ j ];                }            }            MaxLen[ i ] = recordMaxLen + 1;        }        int result = 0;        for( int i = 1; i <= N; i++ )            if( MaxLen[ i ] > result )                result = MaxLen[ i ];        cout <<  result << endl;    }}

  
        动态规划总结:

        动态规划的两个要素:最优子结构 和 重叠子问题。

        最优子结构:一个问题的最优解中包含了子问题的最优解,则该问题具有最优子结构。(这个时候应该可以考虑到动态规划可能使用于解这类题目)。我们可以通过子问题的最优解来构造原问题的一个最优解,So 要保证考虑的子问题范畴中,一定要包含用于一个最优解的那些子问题。

        我们讨论的两个问题当中,都用到了最优子结构。例子1中 到达MaxSum(1,1)的最优路线中,一定包含了到达MaxSum(2,1)或者MaxSum(2,2)的最优路线。

        动态规划算法的运行时间依赖两个因素的乘积。子问题的总个数 和每一个子问题中又多少个选择。

        动态规划以自底向上的方式来利用最优子结构,首先找到子问题的最优解,解决了子 问题,然后再找到问题的最优解。



        


(编辑: m6830098)

网友评论