博客

与动态规划有关的几个概念：

• 
  
  记忆化搜索：对于有重叠子问题的问题，我们把第一次遇到的子问题的值给记录下来，下一次遇到这个相同的子问题时直接使用这个值，这也是这个递归函数开一个二维数组 的作用；
  
  
• 
  
  重叠子问题：一个问题可以划分为若干个子问题，这些子问题又会重复出现；
  
  
• 
  
  最优子结构：如果一个问题的最优解可以由子问题的解构造出来；
  
  
• 
  
  状态无后效性：当前状态记录了历史信息，一旦当前状态确定了，就不会再改变，且未来的决策只能在已有的一个或若干个状态的基础上进行，历史信息只能通过已有的状态去影响未来的决策。（PS：《算法笔记》）
  
  

给出一个经典问题——数塔问题：一共给出了几个程序，有直解输出结果的，还有给出最大值的路径的，也有递归求解的，还有递推求解的：

/**
    数塔问题，
    状态转移方程：dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];
    最优子结构：如果一个问题的最优解可以由子问题的解构造出来；
    1)只输出结果；
    data:
        5
        5
        8 3
        12 7 16
        4 10 11 6
        9 5 3 9 4

        5
        5
        8 3
        12 7 105
        4 10 11 6
        78 5 3 9 4
*/

/**
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cout << "输入塔的层数:\n";
    cin >> n;
    int f[n+1][n+1],dp[n+1][n+1];
    printf("输入%d层塔的值\n",n);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=i;++j)
            cin >> f[i][j];
    for(int i=1;i<=n;++i)
        dp[n][i]=f[n][i];
    for(int i=n-1;i>=1;--i)
        for(int j=1;j<=i;++j)
    {
        dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];
    }
    cout << dp[1][1] << endl;
    return 0;
}
*/

递归解决：

• /**
      2)递归解决
  */
  /**
      记忆化搜索：对于有重叠子问题的问题，我们把第一次遇到的子问题的值给记录下来，
      下一次这个相同的子问题时遇到直接使用这个值，这也是这个递归函数开一个二维数组
      的作用；
  
      重叠子问题：一个问题可以划分为若干个子问题，这些子问题又会重复出现；
      
      最优子结构：如果一个问题的最优解可以由子问题的解构造出来；
  */
  
  /**
  #include <iostream>
  #include <algorithm>
  #include <cstring>
  using namespace std;
  const int maxn=10;
  int f[maxn][maxn],dp[maxn][maxn];
  int n;
  int max_val(int pos,int index)
  {
      memset(*dp,-1,sizeof(dp));
      if(pos==n)
          return f[pos][index]; //如果达到最后一层，返回这个元素的值
      if(dp[pos][index]!=-1)
          return dp[pos][index];
      else
      {
          dp[pos][index]= max(max_val(pos+1,index),max_val(pos+1,index+1))+f[pos][index]; //如果要选这个元素，
          return dp[pos][index];  //则比较下一层紧挨着的两个元素的及后续选择的最大的和，谁大选谁
  
      }
  }
  int main()
  {
      cout << "输入塔的层数:\n";
      cin >> n;
      printf("输入%d层塔的值\n",n);
      for(int i=1;i<=n;++i)
          for(int j=1;j<=i;++j)
              cin >> f[i][j];
      cout << max_val(1,1) << endl;
      return 0;
  }
  */

输出最大值的路径：

/**
    3)输出最大值的路径
*/

/**
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cout << "塔的层数:\n";
    cin >> n;
    int f[n+1][n+1],dp[n+1][n+1];
    for(int i=1;i<=n;++i)
        for(int j=1;j<=i;++j)
            cin >> f[i][j];
    for(int i=1;i<=n;++i)
        dp[n][i]=f[n][i];
    for(int i=n-1;i>=1;--i)
        for(int j=1;j<=i;++j)
    {
        dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];
    }
    cout << "maximum result:\n" << dp[1][1] << endl;
    cout << "path of maxmium:\n" ;
    cout << f[1][1];
    for(int i=1,j=1;i<n;++i)
    {
        cout << " -> ";
        int temp=dp[i][j]-f[i][j];
        if(temp==dp[i+1][j])
            cout << f[i+1][j];
        else
            cout << f[i+1][++j];
    }
    cout << endl;
    return 0;
}
*/

三维数组存储数据，存储，中间处理，输出于一体

/**
    三维数组存储数据，存储，中间处理，输出于一体
*/


#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cout << "塔的层数:\n";
    cin >> n;
    int a[n+1][n+1][3];
    for(int i=1;i<=n;++i)
        for(int j=1;j<=i;++j)
        {
            cin >> a[i][j][0];
            a[i][j][2]=0;   //假设每一层都选择下一层的左边个元素
        }
    for(int i=1;i<=n;++i)
        a[n][i][1]=a[n][i][0];
    for(int i=n-1;i>=1;--i)
        for(int j=1;j<=i;++j)
    {
        a[i][j][1]=max(a[i+1][j][1],a[i+1][j+1][1])+a[i][j][0];
        if(a[i+1][j][1]<a[i+1][j+1][1])
            a[i][j][2]=1;   //如果下一层的右边元素更优，则置为1，选择下一层的右边个元素
    }

    cout << "maximum result:\n" << a[1][1][1] << endl;
    cout << "path of maxmium:\n" ;
    int i,j;
    for( i=1,j=1;i<=n;++i)
    {
        cout << a[i][j][0];
        if(i!=1||i!=n)
            cout << " -> ";
        j+=a[i][j][2];
    }
    return 0;
}