本文共 1991 字，大约阅读时间需要 6 分钟。

1.动态规划学习步骤：

（1）阅读题目找出所需的暴力求解方法（递归调用）。

注：要学会递归调用的关系。 （2）根据题目加入相应的记忆数组，来存储递归过程中访问过的结点。使其重复的过程大大减少。（记忆化的暴力求解方法） （3）而后演变到有规律的进行访问，将访问的结点保存。知道得出结果。 （4）由于步骤三中访问过程是有规律的，使得进一步化简得到可能。在寻找好的方法（时间和空间）。

2.动态规划的题目设计：

（1）此题目来源于北大POJ

数字三角形(POJ1163) 在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。 三角形的行数大于1小于等于100，数字为 0 - 99 输入格式： 5 //表示三角形的行数 接下来输入三角形 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 要求输出最大和 分析思路：首先想到暴力搜索：

用Data[i][j]来存储第i行第j列的数；Max_serch(x,y)表示从x行，y列到底地边个点的路径中，路径之和最大的。则可以通过Max_serch(0,0)递归得到。因为从Data[i][j]出发只能到Data[i+1][j]或Data[i+1][j+1].递归关系式：(1)i或者j为底边行或者列，这就返回Data[i][j].（2）否则就(2)Max_serch(i,j)=max(Max_serch(i+1,j),Max_serch(i+1,j+1))+Data[i][j]。

程序：

int Max_serch(int x,int y){

if(x==n-1||y==n-1){ return Data[x][y]; }else{ return max(Max_serch(x+1,y),Max_serch(x+1,y+1))+Data[x][y]; } }

此时访问的过程没有记忆化，所以会出现大量的重复搜索。

例如：当我们计算第二行2时候的Max_serch（）会计算从7开始的Max_serch（），当我们计算第二行4时候的Max_serch（）也会计算从7开始的Max_serch（），所以出现重复的时候。 C此时想到，引入一个二维数组，将访问过的点存储起来，以便减少访问次数（递归时直接读取数据）。 自然而然引出来记忆化暴力搜索：

程序：

int Max_serch(int x,int y){ memset(Temp,0,sizeof(Temp)); if(Temp[x][y]!=0){ return Temp[x][y]; } if(x==n-1||y==n-1){ return Data[x][y]; }else{ Temp[x][y]=max(Max_serch(x+1,y),Max_serch(x+1,y+1))+Data[x][y]; } return Temp[x][y]; }

进一步考虑有没有更好的方法：将临时存储数据的Temp[x][y]数组：存储的是第x行，第y列最优的解，那么最底一行存的一定是Data[x][y]的数据，那么问题就变成了由下到上逐步求解了。

程序：

#include
   
    using namespace std;int Data[101][101]; int Temp[101][101];int n;int Max_serch(){    memset(Temp,0,sizeof(Temp));    if(n==1)     return Data[0][0];    for(int i=n-1,j=0;j
    
     =0;k--){
           for(int j=k;j>=0;j--){
               Temp[k][j]=max(Temp[k+1][j],Temp[k+1][j+1])+Data[k][j];        }    }    return Temp[0][0];}int main(){   cin>>n;   for(int i=0;i
     
      >Data[i][j];       }   }   int sum;   sum=Max_serch();   cout<
      
       <
      
     
    
   

在最后进行分析不难发现还可以进一步优化（空间优化），那就是将临时变量Temp都不需要只需要一行数组就行，用原始的Data数据中最右列存储。虽然有的题目不可以这样但是这也是一种思考优化的方法。   此外学习动态规划的典型应用也是很有必要的，对于常见的类型我们要直接记住动态规划的方法（最优二叉搜索树，最长公共子序列，钢条切割）

转载地址：https://blog.csdn.net/xiaochen87654321/article/details/59707002 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！