momoizeSearch(non-recursive)

import java.util.ArrayDeque;

public class MaxFee {

  /**
	 * @param args
	 * @throws Exception
	 */
	public static void main(String[] args) throws Exception {

		fees = new int[] { 130, 150, 190, 190, 230, 290, 330, 70, 330, 110, 90,
				310, 330, 190, 230, 170 };
		days = new int[] { 9, 12, 20, 23, 27, 33, 31, 9, 30, 9, 6, 34, 34, 22,
				25, 13 };

//		 fees = new int[] { 130, 150, 190, 190, 230, 290, 330, 70, 330, 110,
//		 90,
//		 310, 330, 190, 230, 170 , 150, 190, 190, 230, 290, 150, 190, 190,
//		 230, 290, 150, 190, 190, 230, 290, 150, 190, 190, 230, 290, 150, 190,
//		 190, 230, 290,
//		 310, 330, 190, 230, 170 , 150, 190, 190, 230, 290, 150, 190, 190,
//		 230, 290, 150, 190, 190, 230, 290, 150, 190, 190, 230, 290, 150, 190,
//		 190, 230, 290,
//		 310, 330, 190, 230, 170 , 150, 190, 190, 230, 290, 150, 190, 190,
//		 230, 290, 150, 190, 190, 230, 290, 150, 190, 190, 230, 290, 150, 190,
//		 190, 230, 290};
//		 days = new int[] { 9, 12, 20, 23, 27, 33, 31, 9, 30, 9, 6,
//		 34, 34, 22,25, 13 , 31, 9, 30, 9, 6, 31, 9, 30, 9, 6, 31, 9, 30, 9,
//		 6, 31, 9, 30, 9, 6, 31, 9, 30, 9, 6,
//		 34, 34, 22,25, 13 , 31, 9, 30, 9, 6, 31, 9, 30, 9, 6, 31, 9, 30, 9,
//		 6, 31, 9, 30, 9, 6, 31, 9, 30, 9, 6,
//		 34, 34, 22,25, 13 , 31, 9, 30, 9, 6, 31, 9, 30, 9, 6, 31, 9, 30, 9,
//		 6, 31, 9, 30, 9, 6, 31, 9, 30, 9, 6};

		// fees = new int[] { 130, 150, 190 };
		// days = new int[] { 9, 12, 20 };
		 
		new MaxFee(fees, days, 100);
	}

	public MaxFee(int[] fee, int[] day, int daysLimit) throws Exception {

		if (fee.length != day.length) {
			throw new Exception("two arguments length differ");
		}

		cache = new int[1000][1000];
		isCached = new boolean[1000][1000];
		long s = System.currentTimeMillis();
		System.out.println(search(daysLimit));
		System.out.println(System.currentTimeMillis() - s + "ms");
		System.out.println(comparingCount);

	}

	private static int[] fees;
	private static int[] days;

	private static int[][] cache;
	private static boolean[][] isCached;
	
	private int callCnt;

	private int comparingCount;

	/**
	 * 再帰を使わず、スタックを使用しメモ化処理を加えた深さ優先探索をする試み
	 * 
	 * @param dayLimit
	 *            　タスクを入れられる残り日数
	 * @return　最も多いFee
	 */
	private int search(int daysLimit) {

		ArrayDeque<Node> stack = new ArrayDeque<>();
		
		stack.push(new Node(0, daysLimit, null, false));

		int ans = 0;

		while (stack.isEmpty() == false) {

			Node node = stack.peek();
//			System.out.println("stack:" + stack.size());

			// 自分はトップのノードではなく、かつ子供ノードから結果を受け取っている場合
			if (node.parent != null && node.numReturned > 0) {
				node.parent.numReturned++;
				int i = 0;
				if (node.isParentFeeAdded) {
					i = 0;
				} else {
					i = 1;
				}
				node.parent.childFee[i] = +Math.max(node.ownFee
						+ node.childFee[0], node.childFee[1]);
				comparingCount++;
				// この結果をメモする
				if (cache[node.currentPosition][node.totalDays] < node.parent.childFee[i]) {
					cache[node.currentPosition][node.totalDays] = node.parent.childFee[i];
				}
				isCached[node.currentPosition][node.totalDays] = true;
				stack.pop();
			} else if (node.parent == null && node.numReturned > 0) {
				// トップのノードであり、子供ノードから結果を受け取った場合ループ抜け、結果返す
				ans = Math
						.max(node.ownFee + node.childFee[0], node.childFee[1]);
				comparingCount++;
				stack.pop();
				break;
			} 
			
			else if (isCached[node.currentPosition][node.totalDays]) {
				// すでに計算された答えがある場合
//				 System.out.println("cached" + (callCnt++));
				if (node.parent != null) {
					int i = 0;
					if (node.isParentFeeAdded) {
						i = 0;
					} else {
						i = 1;
					}
					node.parent.childFee[i] = cache[node.currentPosition][node.totalDays];
					node.parent.numReturned++;
					stack.pop();
				} else {
					// トップノードの場合はループを抜ける
					ans = cache[node.currentPosition][node.totalDays];
					stack.pop();
					break;
				}
			}

			else if (node.currentPosition == fees.length) {
				// タスクがもう選べない場合
				if (node.parent != null) {
					node.parent.numReturned++;
					stack.pop();
				} else {
					break;
				}

			} else if (node.totalDays < days[node.currentPosition]) {
				// 指定されたタスクは残り日数をオーバーしてしまう場合
				// 次のアイテムを試す
				Node notAdded = new Node(node.currentPosition + 1,
						node.totalDays, node, false);
				// 新しい選択肢を自分より前に持ってきて処理
				stack.push(notAdded);

			} else {
				assert node.numReturned == 0;

				// タスクを追加しても残り日数をオーバーしない場合だが、あえて追加しない選択肢を作る
				Node notAdded = new Node(node.currentPosition + 1,
						node.totalDays, node, false);

				// タスクを追加する場合の選択肢を作る
				// タスクを追加したので残りのタスクに使える日数はその分減る
				int remainDays = node.totalDays - days[node.currentPosition];
				Node added = new Node(node.currentPosition + 1, remainDays,
						node, true);

				// ２つの場合の選択肢をスタックに追加し処理をさせる
				stack.push(notAdded);
				stack.push(added);

				// 自身のタスクのfeeを入れておく
				node.ownFee = fees[node.currentPosition];

			}

		}

		return ans;

	}
}

/**
 * Feeや残り日数を管理する　ノード（タスク）クラス
 *
 */
class Node {
	public int currentPosition;
	
	/**
	 * タスクの報酬
	 */
	public int ownFee;
	public int totalDays;


	/**
	 * 合計報酬の報告先となる親ノード
	 */
	public Node parent;
	
	/**
	 * 子ノードが結果を返してきたかを見る。
	 * デフォルトは0。２つの子ノードを持つとき、最大で２
	 * １つでは１
	 */
	public int numReturned;
	
	/**
	 * 2つの子ノード（選択肢）の合計値
	 * 自身のタスクを選んだ場合は[0]に入る
	 * 選ばなかった場合は[1]
	 */
	public int[] childFee = new int[] { 0, 0 };

	/**
	 * 親のfeeが入っている選択肢はtrue　入っていなければfalse
	 */
	public boolean isParentFeeAdded;

	public Node(int count, int day, Node parent, boolean added) {
		currentPosition = count;
		totalDays = day;
		this.parent = parent;
		isParentFeeAdded = added;
	}
}