動的プログラミングで配列内の要素を連結する方法（java）

Question

私は動的アルゴリズムの問​​題があり、私はそれをほぼ解決しました。問題は、私は1を加え、2を掛け、3を乗算する演算しかできないプリミティブな計算機を持っているということです。私は任意の数になるために必要な最小ステップ数を見つけなければなりません。私は問題を正しく実装しましたが、nにつながる数字の配列を出力する必要もあります。つまり、n = 5の場合、ステップは1,2,4,5で3ステップを要したので3を出力する必要があります。私のアルゴリズムは最小限のステップ数を見つけるのに有効ですが、配列を見つけることはできません。私は終わりから始まる分割と征服のアルゴリズムがうまくいくかもしれないと思っていますが、分裂と征服は良くありません。ここに私のコードです。配列全体（nにつながる要素ではなく、すべての要素）を出力します。

public static int min(int a, int b){if(a>b){return b;}else{return a;}} 
public static int min(int a, int b, int c){return min(min(a, b), c);} 
public static int[] primitiveCalc(int n){ 
    int[] solution=new int[n]; 
    solution[0]=0; 
    solution[1]=0; 
    for(int i=2;i<n;i++){ 
     if(i%3==0){ 
      if(i%2==0){solution[i]=min(solution[i-1]+1, solution[i/3]+1, solution[i/2]+1);} 
      else{solution[i]=min(solution[i-1]+1, solution[i/3]+1);} 
     }else if(i%2==0){solution[i]=min(solution[i-1]+1, solution[i/2]+1);} 
     else{solution[i]=solution[i-1]+1;} 
    } 
    System.out.println(solution[n-1]); 
    return solution; 
} 
public static void main(String[] args){ 
    Scanner in=new Scanner(System.in); 
    int n=in.nextInt(); 
    int[] solution=primitiveCalc(n+1); 
    for(int i=1;i<solution.length;i++){ 
     System.out.print(solution[i]+" "); 
    } 
} 

ご了承ください。誰もが興味を持っている場合、私は解決策を持って

は、ここに実装したものです：

私はそこにいることを知っている

public static int[] findChainArray(int[] array, int n){ 
    int[] chainedArr=new int[array.length]; 
    for(int i=array.length-1, j=0;i>0;j++){ 
     if(i%3==0) { 
      if (i % 2 == 0) { 
       if (min(array[i - 1], array[i/2], array[i/3]) == array[i - 1]) { 
        i = i - 1; 
       } else if (min(array[i - 1], array[i/2], array[i/3]) == array[i/2]) { 
        i = i/2; 
       } else { 
        i = i/3; 
       } 
      }else{ 
       if (min(array[i - 1], array[i/3]) == array[i - 1]) { 
        i = i - 1; 
       } else { 
        i = i/3; 
       } 
      } 
     }else if(i%2==0){ 
      if (min(array[i - 1], array[i/2]) == array[i - 1]) { 
       i = i - 1; 
      } else if (min(array[i - 1], array[i/2]) == array[i/2]) { 
       i = i/2; 
      } 
     }else{ 
      i=i-1; 
     } 
     chainedArr[j]=i; 
    } 
    return chainedArr; 
} 

elseとIL試みは、今で

Answer 1

を削減する場合は、有効を持っていることをあまりにも多くのパスを使用すると、後方への作業を試みることができます。

answer = solution[n]から再帰的に作業し、solution[n-1] = answer-1,solution[n/2] = answer-1、またはsolution[n/3] = answer-1かどうかを確認できます。もちろん、あなたがすでにやっているようnは、2または3最初で割り切れるかどうかを確認するために、適切なチェックを行う必要があると思います。

また、あなたはlastと呼ばれる配列を作成することができ、代わりにのみsolutionに各iの最小値を保存するので、あなたもlastでパスの最後の要素を救うことができます。

これは宿題の問題や自分でて動作するようにしようとしている質問のいずれかのように思えるので、私はあなた次第実装の詳細を残しておきますが:)