第6週:動的プログラミングの問題1

✔ BOJ_1463

私はダイナミックプログラミングの定義があまり理解できないので、すぐに問題を解くのではなく、ネット上の解答に基づいてダイナミックプログラミングを理解したいと思っています.
リファレンス
d[n]は、nを1とする最小数を記憶する.再帰関数(topdow)や繰り返し文(bottomup)で求めることができますが、どちらでも(?)見えました.
d[0]およびd[1]は3または2に分割できないか、または1を減算して1を作成するので、d[0]=d[1]=0となる.
この問題には3つの可能な演算があります.
最初の1を減算すると、d[i]=d[i-1]+1(i-1が1の場合、iはi-1に-1を加算しなければならない.したがって、d[i-1]演算回数には、d[i]=d[i-1]+1となるように1回の演算回数が加算される.
2番目の2で割った場合、d[i]=d[i/2]+1となります.
同様に、3をd[i]=d[i/3]+1で割った.
したがって、bottomupコードは次のようになります.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;

public class BOJ_1463{
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n= Integer.parseInt(br.readLine());
        int d[] = new int[n+1];
        d[0] = 0;
        d[1] = 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]);
         }}

次は、これらのコンテンツをtop-downとして記述するコードです.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_1463{
	public static int d[];
    public static void main(String[] args) throws IOException{
    	BUfferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n= Integer.parseInt(br.readLine());
        d = new int[n+1] ;
        System.out.println(calculate(n));}
  [
  public static int calculate(int n){
  	if(n==1) return 0;
    if(d[n] >0 ) return d[n];
    d[n] = calculate(n-1)+1;
    if(n%3==0){
    	d[n] = Math.min(d[n], calculate(n/3)+1);}
   	if(n%2==0){
    	d[n] = Math.min(d[n], calculate(n/2)+1);}
    return d[n];}}