动态规划 - 求解二项式系数(完整代码)

 

1. 动态规划 备忘录法

备忘录方法采用自顶向下方式,为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。

 

/*
@author: jarg
@TODO 动态规划 - 备忘录法 求解二项式系数
*/

import java.io.*;
import java.util.*;

public class Binomial
{
	/*
	Map<K,V>中K,V说明
	K: n,m组成的字符串
	V: value求解出的值
	demo: 备忘录,保存已经求解出的子问题的解
	*/
	public static Vector<Map> demo = new Vector<Map>();

	public static void main(String[] args)
	{
		InputStreamReader ir = new InputStreamReader(System.in);
		try
		{
			System.out.print("输入参数n: ");
			int n = Integer.parseInt("" + (char)ir.read());

			/* 过滤输入参数n时,末尾的回车,换行 */
			if((char)ir.read() == '\r' || (char)ir.read() == '\n')
			{
				ir.read();
			}

			System.out.print("输入参数m: ");
			int m = Integer.parseInt("" + (char)ir.read());

			System.out.println("Binomial("+ n + "," + m +")=" + Binomial(n,m));
		}
		catch(Exception e)
		{
			System.out.println("invalid input.");
		}

	}

	/* 求二项式系数 */
	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);
	}

}

 

2. 动态规划 迭代法:

迭代法采用自底向上方式,保存已求解的子问题,需要时取出,消除对某些子问题的重复求解.

/*
@author: jarg
@TODO: 动态规划 - 求解二项式系数
*/

import java.io.InputStreamReader;

public class Binomial
{
    public static void main(String[] args)
    {
		InputStreamReader ir = new InputStreamReader(System.in);
		try
		{
			System.out.print("输入参数n: ");
			int n = Integer.parseInt("" + (char)ir.read());

			/* 过滤输入参数n时,末尾的回车,换行 */
			if((char)ir.read() == '\r' || (char)ir.read() == '\n')
			{
				ir.read();
			}

			System.out.print("输入参数m: ");
			int m = Integer.parseInt("" + (char)ir.read());

			System.out.println("Binomial("+ n + "," + m +")=" + binomial(n,m));
		}
		catch(Exception e)
		{
			System.out.println("invalid input.");
		}
        
    }

	/* 求二项式系数 */
    public static int binomial(int n, int m)
    {
        int value[] = new int[n+1];
		for(int i=0;i<=n;i++)
		{
			value[i] = 1;

			/* 边界条件m=0,n=m的情况 */
			for(int j=i-1;j>0;j--)
			{
				value[j] = value[j] + value[j-1];
			}
		}
		return value[m];
    }

}