保存结果的最佳方法 - 动态规划
我正在努力解决一个与 Euler Problem 215 有点相似的问题。我想我可以解释这一点，而无需解释整个问题和/或我解决问题的完整方法。
现在我正在使用 RT([Arraylist of Numbers], int i) 进行递归调用。根据该技术，我想保存结果，因此，如果 RT 询问相同的问题，我可以简单地查找答案，而不是重复执行，直到达到基本情况。
只是为了说明 RT([3, 7.5, 10.5, 15], 2)。在递归中，右边的在右边进行自增。 Arraylist 用于识别还需要调用基本情况的内容。
通常，我对动态编程的理解通常使用二维数组，其中使用所谓的参考点来保存和存储结果。如果它是类似 RT(int x, int y) 的东西，那就太好了。但我的问题呢？
我想我可以将 ArrayList 更改为字符串 37510515，然后更改为一些使用的 ASCII 数字或者数字本身。但我希望我可以像 HashMap 一样处理这个问题，其中我使用 ArrayList 作为键，但是这个 HashMap 中的缺陷只适用于一个值（我知道我可以链接，但是它如何在存储结果时起作用）轻松跟踪它被调用的“int i”？）
简而言之，任何人都可以帮我想出一种用 ArrayList 和 int 作为两个引用来存储结果的方法吗？
提前致谢！
I am working to solve a problem that is a bit similar to Euler Problem 215. I think I can explain this without explaining the entire problem and/or my full approach to solving it.
Right now I'm making recursive calls with RT([Arraylist of numbers], int i). As per the technique, I want to save the results, so if and when RT asks for the same problem, I can simple just look up the answer instead of recurring until the base case is reached.
Just to illustrate RT([3, 7.5, 10.5, 15], 2). In the recursion, the right in the right side to increment. The Arraylist is used to identify what else it needs to recall to the base case.
Usaully, my understanding of Dynamic Programming usually uses 2D Arrays where the results are saved and stored using what's being called as the reference point. This is great if it is something like RT(int x, int y). But what about my problem?
I guess I can change the ArrayList to a string 37510515 and then to some used ASCII numbers or perhaps the numbers itself. But I'm hoping I can approach this like a HashMap where I use the ArrayList as a key, but the flaw in this a HashMap only works well with one value (I know I can chain, but how would that work in storing results while easily keeping track of what "int i" it is called on?)
So in short, can anyone help me think of a way to store results with an ArrayList and an int as the two references?
Thanks in advance!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您可以使用任何您喜欢的类的对象作为 HashMap 的键，如果该对象正确定义了 equals() 和 hashCode() ，它将起作用。这些方法已经在 ArrayList 中正确实现，因此您应该发现使用 ArrayList 作为 HashMap 键效果非常好。
如果你想使用 ArrayList 和一个数字组合作为 HashMap 的键，你可以为此定义一个类，在该类中实现 hashCode() 和 equals()，或者通过将数字设置为最后一个来作弊。数组列表中的条目。
听起来你正在做的事情更像 http://en.wikipedia.org/wiki/Memoization 比动态编程好，但它可能会完成工作 - 我猜想欧拉问题已经被设置为使其可以实现最佳技术 - 如果这是记忆或动态编程，你应该会发现它是负担得起的。如果时间太长，那么我们都错过了一些更有效的方法。
进一步加快速度的一种方法是利用问题中的对称性 - 例如，如果您的状态对应于一行（或一列）块，那么这与布局相同块的行的状态至关重要从右到左而不是从左到右，或者从下到上而不是从上到下。
You can use objects of any class you like as keys for a HashMap, and it will work if the object has defined equals() and hashCode() properly. These methods have already been implemented properly in ArrayList, so you should find that using ArrayLists as HashMap keys works perfectly well.
If you want to use an ArrayList and a number combined as a key for a HashMap, you could either define a class for this, implementing hashCode() and equals() in that class, or cheat a bit by making the number just the last entry in the arraylist.
It sounds like what you are doing is more like http://en.wikipedia.org/wiki/Memoization than dynamic programming, but it may get the job done - I guess that the Euler problem has been set to make it doable for the best technique - if that is memoization or dynamic programming you should find it is affordable. It that takes too long, then both of us have missed some more efficient method.
One way of speeding it up further would be to take advantage of symmetries in the problem - e.g. if your state corresponds to a row (or a column) of blocks, then that is essential the same state as the row with the same blocks laid out right to left instead of left to right, or bottom to top instead of top to bottom.
解决问题的一种方法是实现您自己的类包装 arraylist 和 arraylist。 int，如此处所述编写
hashCode和equals。使用字节数组作为映射键
One way to solve is to implement your own class wrapping both arraylist & int, writing
hashCodeandequalsas mentioned here.Using a byte array as Map key