1. 动态规划 备忘录法
备忘录方法采用自顶向下方式,为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。
说明: 在非边界条件下,每次求解子问题时,先查找备忘录.
若子问题已经求解过了,直接取出子问题的解;若未求解过,则求解并保存到备忘录中.
此处的备忘录就是一个存储数据的容器.
public staticint Binomial(int n,int m){ if(n==m || m==0){ return 1;} int date = readDate(n,m); if(date>0){ return date; } else { int result = Binomial(n-1,m) + Binomial(n-1,m-1);writeDate(n,m,result); return result; } } public staticint readDate(int n,int m){ for(int i=0;i<demo.size();i++){ Map<String,Integer> date = new HashMap<String,Integer>();date = demo.get(i); if(date.get("" + n + m) !=null) { return date.get("" + n + m);} } return 0;} public staticvoid writeDate(int n,int m,int value){ Map<String,Integer> date = new HashMap<String,Integer>();date.put("" + n + m,value); demo.add(date); }public static int Binomial(int n,int m)
{
if(n==m || m==0)
{
return 1;
}
int date = readDate(n,m);
if(date>0)
{
return date;
}
else
{
int result = Binomial(n-1,m) + Binomial(n-1,m-1);
writeDate(n,m,result);
return result;
}
}
public static int readDate(int n,int m)
{
for(int i=0;i<demo.size();i++)
{
Map<String,Integer> date = new HashMap<String,Integer>();
date = demo.get(i);
if(date.get("" + n + m) != null)
{
return date.get("" + n + m);
}
}
return 0;
}
public static void writeDate(int n,int m,int value)
{
Map<String,Integer> date = new HashMap<String,Integer>();
date.put("" + n + m,value);
demo.add(date);
}
java
运行
2. 动态规划 迭代法:
迭代法采用自底向上方式,保存已求解的子问题,需要时取出,消除对某些子问题的重复求解.
Pascal三角形:
说明: 在非边界的情况下,二项式系数=上一行同列数值+上一行同列前一个数值.
为了节省空间,根据n的大小,定义长度为n+1的整型数组,用以存储子问题的解.
从后往前计算图中二项式系数的解,完成后,将问题解存储在数组中对应的列标号位置.
public staticint binomial(int n,int m) { int value[] = newint[n+1];for(int i=0;i<=n;i++){ value[i] = 1; for(int j=i-1;j>0;j--){ value[j] = value[j] + value[j-1];} } return value[m]; }
