首页 > 代码库 > Beauty Of algorithms（七）动态规划 钢条分割 矩阵链乘 最长公共子序列 最优二叉树
Beauty Of algorithms（七）动态规划 钢条分割 矩阵链乘 最长公共子序列 最优二叉树
1.动态规划
动态规划的方法与方法类似，英文“dynamic programming”，这里的programming不是程序的意思，而是一种表格法。都是通过组合子问题的解来解决原问题，分治方法将划分为互不相交的子问题，递归的求解子问题，再将它们的解组合起来求出原问题的解。与之相反动态规划应用于子问题的重叠情况，即不同的子问题具有公共的子问题，子问题的求解是递归进行 的，将其划分为更小的子问题，动态规划，每个子问题只求解一次，将其保存在表格中，从而无需每次求解子问题时都重新计算。两种等价的实现方法：带备忘录的自顶向下法，和自底向上法。
动态规划常用来求解最优化问题。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找最优值。我们通常按如下四个步骤设计一个动态规划算法：
1.刻画一个最优解的特征。
2.递归的定义最优解的值。
3.计算最优解的值，通常采用自底向上的方法。
4.利用计算出的信息构造出左右解。
2.钢条切割
下面给出 几种不同的算法。
这种算法时间复杂度较高可以用递归树表示：
<span style="font-size:18px;">/**
* @param p：每块长度对应 的价格数组
* @param n：要分割的钢筋长度
* 这种分割方法有很多重复性的计算 不如1 3和 3 1这应该是一种分割方式，但是
* 分割了两次所以会降低运行效率，特别是n变长时，时间增长的非常多
*每一种自顶向下的递归，都能写成从最小资问题开始求解的循环这里 就不在覆写
*/
public int cutRod(int []p,int n)
{
if(n==0)
return 0;
int price=-100;
for(int i=1;i<=n;i++)
{
if(price<p[i]+cutRod(p, n-i))
price=p[i]+cutRod(p, n-i);
}
return price;
}</span>下面使用动规的两种算法：
/** 使用动态规划的方法求解
* 为了解决上一层当中的已经计算过的值仍旧计算的情况，当一种长度的最优解求出时
* 就记录在数组中，当检查到数组中已存在值就返回。
*
* @param p：每个长度的钢筋对应的价格
* @param n：要切割钢筋的长度
* @param r：保存以求出的子问题的最优解的值（一个备忘录）
*/
public int memoizedCutRod(int []p,int n,int r[])
{
if(n==0)
{
r[0]=0;
return r[0];
}
if(r[n]>=0)
return r[n];
int price =-100;
for(int i=1;i<=n;i++)
if(price<p[i]+memoizedCutRod(p, n-i,r))
price=p[i]+memoizedCutRod(p, n-i,r);
r[n]=price;
return price;
}
/** 动态规划的第二种解法，自底向上法，也就是递归的循环实现，从底向下依次求出
* 最优解，这种方法更直观，递归问题，当前的求解都依赖于前面问题的解
* 这个方法比前面两个方法增加了，最优解时的划分数组s，以及当每次切割时需要花费
* a时的最优解情况。
* @param p
* @param n
* @param r
* @param s：存储最优解得划分方案
*/
public int bottomUpCutRod(int p[],int n,int r[],int s[],int a)
{
r[0]=0;
int i;
for(int j=1;j<=n;j++)
{
int price=-100;
for(i=1;i<=j;i++)
{
if(price<p[i]+r[j-i])
{
price=p[i]+r[j-i];//分割问题，左半边为i，右半边为n-i
s[j]=i;
}
}
if(s[j]!=j)//每次其实只分割一次，从i分割，然后加上n-i的最优解，n-i
price-=a;//为子问题，切割的经费已经减去。这就是递归以及
r[j]=price; //自底向上的优势
}
return r[n];
}
public void printSolution(int []s,int n)
{
while(n>0)
{
System.out.print(s[n]+" ");
n=n-s[n];
}
}Beauty Of algorithms（七）动态规划 钢条分割 矩阵链乘 最长公共子序列 最优二叉树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。