动态规划入门（dp）

dp的基本思想，是把大问题转化成一个个小问题，然后递归解决。

所以本质思想的话还是递归。

dp最重要的是要找到状态转移方程，也就是把大问题化解的过程。

举个例子

一个数字金字塔

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

这个题不难想到，你只要找出每一步的最大值就可以。·

那么这么找呢？（递归啊~）

我们先看看状态转移方程

/*

首先，肯定得用二维数组来存放数字三角形

    然后我们用D( r, j) 来表示第r行第 j 个数字(r,j从1开始算)

    我们用MaxSum(r, j)表示从D(r,j)到底边的各条路径中，最佳路径的数字之和。

    因此，此题的最终问题就变成了求 MaxSum(1,1)

    当我们看到这个题目的时候，首先想到的就是可以用简单的递归来解题：

    D(r, j)出发，下一步只能走D(r+1,j)或者D(r+1, j+1)。故对于N行的三角形，我们可以写出如下的递归式：

*/

if ( r == N)

    MaxSum(r,j) = D(r,j)

else

    MaxSum( r, j) = Max{ MaxSum(r＋,j), MaxSum(r+,j+) } + D(r,j)

那么是不是就可以了？

 #include <iostream>

 #include <algorithm>

 #define MAX 101

 using namespace std;

 int D[MAX][MAX];

 int n;

 int MaxSum(int i, int j){

     if(i==n)

         return D[i][j];

     int x = MaxSum(i+,j);

     int y = MaxSum(i+,j+);

     return max(x,y)+D[i][j];

 }

 int main(){

     int i,j;

     cin >> n;

     for(i=;i<=n;i++)

         for(j=;j<=i;j++)

             cin >> D[i][j];

     cout << MaxSum(,) << endl;

 }

但实际上，这个代码会超时的。

为什么呢，

因为已经走过的路，存在重复遍历了

那就把已经遍历过的做一下标记，就可以避免重复遍历了。

 #include <iostream>

 #include <algorithm>

 using namespace std;  

 #define MAX 101  

 int D[MAX][MAX];

 int n;

 int maxSum[MAX][MAX];  

 int MaxSum(int i, int j){

     if( maxSum[i][j] != - )

         return maxSum[i][j];    //如果是-1那说明这个肯定不是目标，直接回去就行了

     if(i==n)

         maxSum[i][j] = D[i][j];

     else{

         int x = MaxSum(i+,j);

         int y = MaxSum(i+,j+);

         maxSum[i][j] = max(x,y)+ D[i][j];

     }

     return maxSum[i][j];

 }

 int main(){

     int i,j;

     cin >> n;

     for(i=;i<=n;i++)

         for(j=;j<=i;j++) {

             cin >> D[i][j];

             maxSum[i][j] = -;   //这里把所有的都设置为-1         }

     cout << MaxSum(,) << endl;

 }

巴特西

动态规划入门（dp）

最新文章

热门文章