java - 如何在动态规划中链接数组中的元素(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;
}

我知道有太多 if else 并且我会尝试减少它

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 中。

因为这看起来像是家庭作业问题或您正在尝试自己解决的问题，所以我将把实现细节留给您:)