[コケ]製作13-1

1として作成

整数Xには、次の3つの演算があります.
1.Xを3で割って、3で割った.
2.Xを2で割り、2で割ります.
1を減らす.
ある整数N上で上記演算を選択し、1を生成しようとする.演算回数の最小値を使う問題を求めます.
X -> X/3
X -> X/2
X -> X-1
大きな問題->小さな問題の答えを利用する.

点火式定義

D[N]=Nが1の最小演算回数である.

Xを3で割って3で割った.

N -> N/3 -> .... -> 1 => D[N]

N/3 -> ... -> 1 => D[N/3]

1 + D[N/3]

Xを2で割って2で割った.

N -> N/2 -> .... -> 1 => D[N]

N/2 -> ... -> 1 => D[N/2]

1 + D[N/2]

1を減算します.

N -> N-1 -> ... ->1

1 + D[N-1]

D[N] = min(D[N/3]+1 , D[N/2]+1, D[N-1] + 1)

N>=2.

Nを3を2で割る優先順位で1にする.

この方法では正解が得られない.(反例10)

は常に最小を求める方法でDynamicで解くとよい.
重要なのは、小さくなることができるすべての状況を確認することです!!

*top-down

再帰関数では、条件の中で最も重要なのは、最小の問題を処理するために条件文が必要であることです.

if(n==1) return 0;

memoization

if(d[n]>0) return d[n];

*bottom-up

の最小サイズの0に初期化すると、ますます大きな問題で計算され、値が見つかります.

通常top-downは耳にあり、bottom-upは複文で解けます.
まずbottom-up法で解く.

import java.util.*;

public class Main {
	public static void main(String[] args)  {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int d[] = new int[n+1];
		d[0]=1;
		d[0]=1;
		for(int i=2;i<=n;i++) {
			d[i]=d[i-1]+1;
			if(i % 2 ==0)
				d[i]=Math.min(d[i], d[i/2]+1);
			if(i % 3 ==0)
				d[i]=Math.min(d[i], d[i/3]+1);
		}
		System.out.println(d[n]);
	}
}

うん...トップダウン法で解くとタイムアウトしました.

import java.util.*;

public class Main {
	static int d[];
	public static void main(String[] args)  {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		d = new int[n+1];
		System.out.println(cal(n));
	}
	
	public static int cal(int n) {
		if(n==1) 	return 0;
		if(d[n]>0)	return d[n];
		
		d[n]=cal(n-1) +1;
		
		if(n%3==0) {
			d[n]=Math.min(d[n], cal(n/3)+1);
		}
		if(n%2==0) {
			d[n]=Math.min(d[n], cal(n/2)+1);
		}
		return d[n];
		
	}
}

理由は、、、数学です.min関数のためです.ほほほ

import java.util.*;

public class Main {
	public static int d[];
	public static void main(String[] args)  {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		d = new int[n+1];
		System.out.println(cal(n));
	}
	
	public static int cal(int n) {
		if(n==1) 	return 0;
		if(d[n]>0)	return d[n];
		
		d[n]=cal(n-1) +1;
		
		if(n%3==0) {
			int tmp=cal(n/3)+1;
			if(d[n]>tmp) {
				d[n]=tmp;
			}
		}
		if(n%2==0) {
			int tmp=cal(n/2)+1;
			if(d[n]>tmp) {
				d[n]=tmp;
			}
		}
		return d[n];
	}
}

これは崔伯俊先生のコードテストの基礎科目に基づいて書いた文章です.