问题标签 [dynamic-programming]

给定的是三个维度 ( , , )中的n框。目标是将它们堆叠在一起以获得最大高度（盒子可以旋转）。您放在顶部的每个盒子的尺寸 ( , ) 都应该比下面的盒子小。hwdwd

我们如何用动态规划和贪婪来做到这一点？

这是我关于最大 L 总和的第一个问题，这是它的不同且困难的版本。

问题：给定一个mxn 正整数矩阵，求从第 1 行到第m 行的最小 L 和。L(4项)喜欢象棋马步

示例：M = 3x3

0 1 2

1 3 2

4 2 1

可能的 L 步是：(0 1 2 2), (0 1 3 2) (0 1 4 2) 我们应该从第 1行到第3行，总和最小

我用动态编程解决了这个问题，这是我的算法：

1.取一个mxn另一个Minimum L Moves Sum数组并复制主矩阵的第一行。我称之为（MLMS） 2.从第一个单元格开始，向上查找 L 移动并计算它
3.如果它小于存在值，则将其插入 MLMS
4.执行步骤 2. 直到第 m行
5.选择最小值在第m行求和

让我逐步解释我的示例：

1. M[ 0 ][ 0 ] sum(L1 = (0, 1, 2, 2)) = 5 ; 总和（L2 =（0,1,3,2））= 6；所以 MLMS[ 0 ][ 1 ] = 6
   sum(L3 = (0, 1, 3, 2)) = 6 ; 总和（L4 =（0,1,4,2））= 7；所以 MLMS[ 2 ][ 1 ] = 6
   

2. M[ 0 ][ 1 ]总和（L5 = (1, 0, 1, 4)) = 6; 总和（L6 =（1,3,2,4））= 10；所以 MLMS[ 2 ][ 2 ] = 6
   

   ... 最后一个 MSLS 是：
   0 1 2
   4 3 6
   6 6 6
   这意味着 6 是从 0 到 m 可以达到的最小 L 和。

我认为它是O(8*(m-1) n) = O(m n)。是否有适合此问题的最佳解决方案或动态规划算法？

谢谢，对不起，很长的问题

这是标记为动态规划的问题（给定一个数字 N，找到将其写为两个或多个连续整数之和的方法数）和示例 15 = 7+8, 1+2+3+4+ 5、4+5+6

我用这样的数学解决了：

a + (a + 1) + (a + 2) + (a + 3) + ... + (a + k) = N

(k + 1)*a + (1 + 2 + 3 + ... + k) = N

(k + 1) a + k (k+1)/2 = N

(k + 1)*(2*a + k)/2 = N

然后检查如果 N 可被 (k+1) 和 (2*a+k) 整除，那么我可以在 O(sqrt(N)) 时间内找到答案

这是我的问题，你如何通过动态编程来解决这个问题？什么是复杂度（O）？

PS：对不起，如果这是一个重复的问题。我搜索但我能找到

我知道这Knapsack是 NP 完全的，而 DP 可以解决它。他们说 DP 解决方案是pseudo-polynomial，因为它是“输入长度”的指数（即编码输入所需的位数）。不幸的是我没有得到它。谁能pseudo-polynomial慢慢给我解释一下？

这是来自的问题

ACM 国际大学生程序设计大赛亚洲区域赛，横滨，2006-11-05

从 x 开始并反复乘以x，我们可以计算出x^3130 次乘法：

编写一个程序，x^n 从x给定的正整数n和n<=200

对于 n = 31，最少 #operations 是 6
对于 n = 50，最少 #operations 是 7

欢迎任何想法。

假设 S = 5 和 N = 3，解决方案看起来像 - <0,0,5> <0,1,4> <0,2,3> <0,3,2> <5,0,0> < 2,3,0> <3,2,0> <1,2,2> 等等

一般情况下，可以使用N个嵌套循环来解决问题。运行 N 个嵌套循环，在其中检查循环变量是否加到 S。

如果我们不提前知道 N，我们可以使用递归解决方案。在每一级中，从 0 到 N 运行一个循环，然后再次调用函数本身。当我们达到 N 的深度时，看看得到的数字加起来是否等于 S。

还有其他动态规划解决方案吗？

我正在尝试找到解决以下问题的最佳方法。通过最好的方式，我的意思是不那么复杂。

作为输入元组列表（开始，长度），如：

每个元素通过它的start和length表示一个序列，例如 (5,7) 等价于序列(5,6,7,8,9,10,11)- 一个以 5 开头的 7 个元素的列表。可以假设元组是按start元素排序的。

输出应返回表示最长连续序列的元组的非重叠组合。这意味着，解决方案是范围的子集，没有重叠和间隙，并且可能是最长的——尽管可能有多个。

例如对于给定的输入，解决方案是：

[(0,5),(5,7)]相当于(0,1,2,3,4,5,6,7,8,9,10,11)

它是回溯解决这个问题的最佳方法吗？

我对人们可能提出的任何不同方法感兴趣。

此外，如果有人知道这个问题的正式参考或另一个类似的参考，我想获得参考。

顺便说一句 - 这不是家庭作业。

编辑

只是为了避免一些错误，这是另一个预期行为的例子

[(0,1),(1,7),(3,20),(8,5)]对于像正确答案这样的输入[(3,20)]等效于长度为 20 的 (3,4,5,..,22)。收到的一些答案将[(0,1),(1,7),(8,5)]等效于 (0,1,2,...,11,12)作为正确答案。但是最后一个答案是不正确的，因为它比 短[(3,20)]。

我需要在 C# 中创建一个动态代理。我希望这个类包装另一个类，并采用它的公共接口，转发对这些函数的调用：

这是我想使用它的方式：

生产：

有任何想法吗？

最简单的方法是什么？

最好的方法是什么？

非常感谢。

更新

我尝试遵循 Wernight 的建议并使用 C# 4.0 动态代理来实现它。不幸的是，我仍然被困住了。代理的重点是模仿（通常，通常）预期的其他接口。使用 DynamicObject 需要我将所有客户端更改为使用“动态”而不是“ISecondaryInterface”。

有没有办法获得一个代理对象，这样当它包装一个 A 时，它（静态地？）宣传它支持 A 的接口；当它包装一个B时，它会宣传支持B的接口？

更新 2

例如：

这是问题

给你一个 1 ≤ N ≤ 50 的数字。每张票都有其 2N 位数字。如果票的前 N ​​位数字之和等于其最后 N 位数字之和，我们称该票为幸运票。您还将获得该号码中所有数字的总和。你的任务是计算一定数量的幸运数字，所有数字的总和都是指定的。

对于输入 2 2 输出为 4 (0101, 0110, 1001, 1010)

你能帮我解决这个问题吗？最小复杂度是多少？

明天我将作为新人编写在线 Google 测试。显然，他们肯定会问一个关于动态编程的问题？

有谁知道在 C 中收集 DP 问题以及解决方案的好资源？我知道 DP 是什么，并且曾经使用过一两次。但是我觉得在测试中破解一个DP问题，典型问题的先前实践将使其更容易接近。

任何具有 C 语言解决方案的好的资源或问题集都将受到高度赞赏。谢谢。