动态编程是所有关于这样一种方式,如果你知道答案,原来的缩小版,你可以用它来回答的主要问题定义问题更快/更直接。这就像应用数学归纳。
在您的特定问题中,我们可以将MinLen(n)定义为n的最小长度表示。接下来说,既然我们想解MinLen(12),假设我们已经知道了MinLen(1),MinLen(2),MinLen(3),...,MinLen(11)的答案。我们如何用这些小问题的答案来找出MinLen(12)?这是动态规划的另一半 - 弄清楚如何使用较小的问题来解决更大的问题。如果你想出一些小问题,但它无法帮助你,但无法将它们结合在一起。
对于这个问题,我们可以做一个简单的说法,“对于12,它是最小长度表示DEFINITELY中有1^2,2^2或3^2。”一般而言,n的最小长度表示将作为其一部分具有小于或等于n的一些正方形。可能会有更好的语句可以提高运行时间,但我会说现在已经足够好了。 MinLen(12)= 1^2 + MinLen(11),OR 2^2 + MinLen(8),OR 3^2 + MinLen(3)这个表述意味着MinLen(12)= 1^2 + MinLen(11),OR2^2 + MinLen你检查它们并选择最好的一个,现在你将它保存为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。越大,它越糟糕。
解决这个问题的方法是让您快速解决n = 1,000,000或更多的问题,即使用名为Memoization的技术。这意味着一旦我们找出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;
}
}
花了我的程序约5秒跑n = 100,000。显然,如果我们希望速度更快,并且要解决更大的问题,还有更多的工作要做。现在的主要问题是,在存储以前答案的全部结果列表时,我们用尽了大量内存。而所有这些复制!你可以做更多的事情,比如只存储一个整数和一个指向子问题的指针,但我会让你这样做。
而由by,1000 = 30^2 + 10^2。
该主题的错误名称 – MBo 2015-03-31 06:56:15