超详细！动态规划详解分析（典型例题分析和对比，附源码） |
您所在的位置：网站首页 › 景区规划案例分析题 › 超详细！动态规划详解分析（典型例题分析和对比，附源码） |
超详细！动态规划详解分析（典型例题分析和对比，附源码）
|
为啥要使用动态规划？什么时候使用动态规划？以下是我的一些理解和心得，如果你感兴趣，就接着往下看吧。 对您有帮助的话记得给我点个赞哟！ 动态规划（Dynamic Programming,DP）算法通常用于求解某种具有最优性质的问题。在这类问题中，可能会有许多可行解，每一个解都对应一个值，我们希望找到具有最优值的解。 动态规划算法与分治法类似，其基本思想也是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解中 得到原有问题的解。与分治法不同的是，动态规划经分解后得到的子问题往往 不是相互独立 的。 （分治算法也可以解决分解后得到的子问题不是相互独立的情况，只是要对公共子问题进行单独求解。这样会使分治法求解问题的复杂度大大提高。对此类问题如果感兴趣的话可以看我的另外一篇文章——分治法详细讲解。） 为什么要使用动态规划算法？有些问题明明可以用递归实现，为什么还要用动态规划实现呢？下面我们看一个经典的例子： 例：斐波拉契数列Fibonacci（斐波拉契数列）问题，它是一个简单而典型的分治问题，Fibonacci数列的递归方程表示为： 递归实现代码： #include int main(){ int F(int n); printf("%d\n",F(5)); return 0; } //Fibonacci数列的递归算法 int F(int n){ if(n return F(n-1)+F(n-2); } }该程序实现简单，但是效率非常低。因为在递归调用过程中，有些子问题被反复计算多次，例如 ： 其中F（3）被计算了两次 F（4）=F（3）+F（2） F（3）=F（2）+F（1）； 那怎样解决这个问题呢？ 如果用一个数组保存已解决的子问题的答案，而在需要的时候再从数组中查找出已求得子问题的答案，这样就可以避免大量的重复计算。这种就是动态规划算法： 动态规划算法代码： #include int main(){ int Fibonacci(int n); printf("%d\n",Fibonacci(5)); return 0; } int Fibonacci(int n){ //申请一个数组存放子问题的解 int f[n+1],i; f[0]=1; f[1]=1; for(i=2;i void tanxin(int a[5][5],int h,int l);//传入数组进行贪心选择 h为行数，l为列数 int i,j; //数组填入采用初始化的形式(今天不是主角) int num[5][5]={0};//全部初始化为0 num[0][0]=9; num[1][0]=12;num[1][1]=15; num[2][0]=10;num[2][1]=6;num[2][2]=8; num[3][0]=2;num[3][1]=18;num[3][2]=9;num[3][3]=5; num[4][0]=19;num[4][1]=7;num[4][2]=10;num[4][3]=4;num[4][4]=16; //初始化完毕 //输出数组 printf("输出初始化过后的数组\n"); for(i=0;i if(num[i][j]!=0) printf("%d ",num[i][j]); } printf("\n"); } //贪心选择开始 tanxin(num,5,5); printf("贪心算法计算的数字和为：%d\n",result); return 0; } void tanxin(int a[5][5],int h,int l){ //拿到数组进行选择 result=a[0][0]; int i,j; for(i=1;i if(a[i+1][j]>=a[i+1][j+1]) result=result+a[i+1][j]; else result=result+a[i+1][j+1]; } } return result; } 动态规划实现我们自底向上，逐层递推，把较大的数字与上一层相加，把得到的数字存到解的数组中（避免重复计算），加到最后就是本题最优解。 例如：
对于num[i][j],比较num[i-1][j],num[i-1][j-1]哪个大，num[i][j]与哪个相加 题中我从num[3][0]开始，与下面的num[4][0]与 num[4][1]比较，因为num[4][0]比较大，num[4][0]与num[3][0]相加 源代码： //动态规划实现数字三角形 #include int result=0; int main(){ //自底向上，眼着全局 int dongtaiguihua(int a[5][5],int h,int l); //数组填入采用初始化的形式(今天不是主角) int num[5][5]={0};//全部初始化为0 num[0][0]=9; num[1][0]=12;num[1][1]=15; num[2][0]=10;num[2][1]=6;num[2][2]=8; num[3][0]=2;num[3][1]=18;num[3][2]=9;num[3][3]=5; num[4][0]=19;num[4][1]=7;num[4][2]=10;num[4][3]=4;num[4][4]=16; //初始化完毕 result=dongtaiguihua(num,5,5); printf("动态规划计算的数字和为：%d\n",result); return 0; } int dongtaiguihua(int a[5][5],int h,int l){ int i,j; for(i=h-2;i>=0;i--){ for(j=0;j |
在图中，19+2>7+2,所以把19与上一层相加
自底向上，逐层向上相加，并把计算的结果存储到结果数组中。 关键：【本文地址】
今日新闻 |
推荐新闻 |