java - 如何改进这段代码？

Question

我开发了一个代码，用于根据 2 的幂来表示数字，我在下面附上相同的代码。

但问题是表达的输出应该是最小长度。

我得到的输出为 3^2+1^2+1^2+1^2 这不是最小长度。我需要以这种格式输出:

package com.algo;
import java.util.Scanner;

public class GetInputFromUser {
    public static void main(String[] args) {
    // TODO Auto-generated method stub
        int n;
        Scanner in = new Scanner(System.in);

        System.out.println("Enter an integer");
        n = in.nextInt();

        System.out.println("The result is:");
        algofunction(n);
    }

    public static int algofunction(int n1)
    {
        int r1 = 0;
        int r2 = 0;
        int r3 = 0;
        //System.out.println("n1: "+n1);
        r1 = (int) Math.sqrt(n1);
        r2 = (int) Math.pow(r1, 2);
        // System.out.println("r1: "+r1);
        //System.out.println("r2: "+r2);
        System.out.print(r1+"^2");

        r3 = n1-r2;
        //System.out.println("r3: "+r3);
        if (r3 == 0)
            return 1;

        if(r3 == 1)
        {
            System.out.print("+1^2");
            return 1;
        } 
        else {
            System.out.print("+");
            algofunction(r3);
            return 1;
        }
    }
}

Answer 1

动态编程就是这样定义问题，如果您知道原始版本的较小版本的答案，您可以使用它更快/更直接地回答主要问题。这就像应用数学归纳法。

在您的特定问题中，我们可以将 MinLen(n) 定义为 n 的最小长度表示。接下来，假设我们要求解 MinLen(12)，假设我们已经知道 MinLen(1)、MinLen(2)、MinLen(3)、...、MinLen(11) 的答案。我们如何使用这些较小问题的答案来计算 MinLen(12)？这是动态规划的另一半——弄清楚如何使用较小的问题来解决较大的问题。如果您提出一些较小的问题，但又无法将它们重新组合在一起，这对您没有帮助。

对于这个问题，我们可以做一个简单的陈述，“对于 12，它的最小长度表示肯定有 1^2、2^2 或 3^2。”而且一般来说，n的最小长度表示都会有一些小于等于n的平方作为它的一部分。您可能可以做出更好的声明，这将改进运行时，但我会说它现在已经足够好了。

此语句表示 MinLen(12) = 1^2 + MinLen(11)，或 2^2 + MinLen(8)，或 3^2 + MinLen(3)。您检查所有这些并选择最好的一个，现在将其保存为 MinLen(12)。现在，如果您想求解 MinLen(13)，您也可以这样做。

独奏时的建议:我自己测试这种程序的方法是插入1、2、3、4、5等，看第一次出错。此外，对于我碰巧认为是个好主意的任何假设，我提出疑问:“小于 n 的最大平方数真的会在 MinLen(n) 的表示中吗？”

您的代码:

r1 = (int) Math.sqrt(n1);
r2 = (int) Math.pow(r1, 2);

体现了该假设(一个贪婪的假设)，但它是错误的，正如您在 MinLen(12) 的答案中清楚地看到的那样。

相反，你想要更像这样的东西:

public ArrayList<Integer> minLen(int n)
{
    // base case of recursion
    if (n == 0)
        return new ArrayList<Integer>();

    ArrayList<Integer> best = null;
    int bestInt = -1;
    for (int i = 1; i*i <= n; ++i)
    {
        // Check what happens if we use i^2 as part of our representation
        ArrayList<Integer> guess = minLen(n - i*i);

        // If we haven't selected a 'best' yet (best == null)
        // or if our new guess is better than the current choice (guess.size() < best.size())
        // update our choice of best
        if (best == null || guess.size() < best.size())
        {
            best = guess;
            bestInt = i;
        }
    }

    best.add(bestInt);
    return best;
}

然后，一旦您有了列表，就可以对其进行排序(不能保证它按排序顺序排列)，然后按照您想要的方式打印出来。

最后，您可能会注意到，对于您插入到上述递归中的较大的 n 值(1000 可能太大)，它会开始变得非常慢。这是因为我们不断地重新计算所有的小子问题——例如，我们在调用 MinLen(4) 时计算出 MinLen(3)，因为 4 - 1^2 = 3。但我们计算出 MinLen(7) 的两次-> 3 = 7 - 2^2，但 3 也是 7 - 1^2 - 1^2 - 1^2 - 1^2。规模越大，情况就越糟。

解决这个问题的方法是使用一种称为 Memoization 的技术，它可以让您非常快速地解决 n = 1,000,000 或更多的问题。 .这意味着一旦我们计算出 MinLen(3)，我们就将它保存在某个地方，比方说一个全局位置以使其更容易。然后，每当我们尝试重新计算它时，我们首先检查全局缓存以查看我们是否已经这样做了。如果是这样，那么我们就使用它，而不是重做所有的工作。

import java.util.*;

class SquareRepresentation
{
    private static HashMap<Integer, ArrayList<Integer>> cachedSolutions;
    public static void main(String[] args)
    {
        cachedSolutions = new HashMap<Integer, ArrayList<Integer>>();
        for (int j = 100000; j < 100001; ++j)
        {
            ArrayList<Integer> answer = minLen(j);
            Collections.sort(answer);
            Collections.reverse(answer);
            for (int i = 0; i < answer.size(); ++i)
            {
                if (i != 0)
                    System.out.printf("+");
                System.out.printf("%d^2", answer.get(i));
            }
            System.out.println();
        }
    }

    public static ArrayList<Integer> minLen(int n)
    {
        // base case of recursion
        if (n == 0)
            return new ArrayList<Integer>();

        // new base case: problem already solved once before
        if (cachedSolutions.containsKey(n))
        {
            // It is a bit tricky though, because we need to be careful!
            // See how below that we are modifying the 'guess' array we get in?
            // That means we would modify our previous solutions! No good!
            // So here we need to return a copy
            ArrayList<Integer> ans = cachedSolutions.get(n);
            ArrayList<Integer> copy = new ArrayList<Integer>();
            for (int i: ans) copy.add(i);
            return copy;
        }

        ArrayList<Integer> best = null;
        int bestInt = -1;
        // THIS IS WRONG, can you figure out why it doesn't work?:
        // for (int i = 1; i*i <= n; ++i)
        for (int i = (int)Math.sqrt(n); i >= 1; --i)
        {
            // Check what happens if we use i^2 as part of our representation
            ArrayList<Integer> guess = minLen(n - i*i);

            // If we haven't selected a 'best' yet (best == null)
            // or if our new guess is better than the current choice (guess.size() < best.size())
            // update our choice of best
            if (best == null || guess.size() < best.size())
            {
                best = guess;
                bestInt = i;
            }
        }

        best.add(bestInt);

        // check... not needed unless you coded wrong
        int sum = 0;
        for (int i = 0; i < best.size(); ++i)
        {
            sum += best.get(i) * best.get(i);
        }
        if (sum != n)
        {
            throw new RuntimeException(String.format("n = %d, sum=%d, arr=%s\n", n, sum, best));
        }

        // New step: Save the solution to the global cache
        cachedSolutions.put(n, best);

        // Same deal as before... if you don't return a copy, you end up modifying your previous solutions
        // 
        ArrayList<Integer> copy = new ArrayList<Integer>();
        for (int i: best) copy.add(i);
        return copy;
    }
}

我的程序运行 n = 100,000 大约需要 5 秒。显然，如果我们想让它更快，并解决更大的 n，还有更多工作要做。现在的主要问题是，在存储以前答案的整个结果列表时，我们会占用大量内存。还有所有的复制!您可以做更多的事情，比如只存储一个整数和一个指向子问题的指针，但我会让您这样做。

顺便说一下，1000 = 30^2 + 10^2。