标签: dynamic-programming

我有一个元素数组[(A1, B1), ..., (An, Bn)]（全部都是正浮点数且 Bi <= 1），我需要找到这样的排列来最小化 sum A1 + B1 * A2 + B1 * B2 * A3 + ... + B1 * ... B(n-1) * An。

当然，我可以尝试所有这些并选择给出最小总和的一个（这将在 O(n!) 中给出正确的结果）。

我尝试将总和更改为A1 + B1 * (A2 + B2 * (A3 + B3 * (... + B(n-1) * An))并尝试使用贪婪算法，该算法在每个步骤中获取最大的 Ai 元素（这不会产生正确的结果）。

现在，当我查看最新的方程时，我认为在这里我看到了最佳子结构A(n - 1) + B(n - 1) * An，因此我必须使用动态规划，但我无法找出正确的方向。有什么想法吗？

编写一个程序，将网格的宽度、W 和高度 H 作为输入，并输出用 (2x1) 多米诺骨牌平铺 W×H 网格的不同方式的数量

我知道如何用 3 x N 网格解决问题，但是为此编写递归公式对我来说太难了！

我不知道该怎么做！

我创建了两个函数 F(n) - 平铺直到 N 的完整方法和 S(n) 用于 3 x N 的不完全平铺方法的数量！但这里由于高度是可变的我想不出任何东西

约束：(0 \xe2\x89\xa4 W+H \xe2\x89\xa4 22)

我在一条线上得到了 n 个点及其位置。我需要计算每对点之间的距离之和。是否可以实现复杂度为 O(n) 的操作？

示例：给定三个点，其坐标为 a(-1)、b(-3)、c(3)。所需金额： |-1 + 3| + | - 1 - 3| + |-3 - 3 | = 12

请帮我。

我想知道幂集问题能否转化为背包问题？在我看来，它们是相同的，例如，我们可以将其视为幂集，即每个递归阶段都会启动 2 个递归调用（一个采用 thi元素，另一个绕过它）。我也可以像背包问题一样用动态规划来解决它，所以这让我想知道是否所有幂集问题都可以转化为背包问题。那是对的吗 ？

以下是硬币变化的代码片段，其中一个具有 O(2 ^N ) 时间复杂度，另一个具有 O(N ² ) 运行时间的动态编程。

// O(2^N) time complexity
void bruteforce(int[] coins, int i, int N, String expr) 
{
     if (i == coins.length) {
         if (N == 0)
            count++;
         return;
     }

     if (N >= coins[i])
         recursion(coins, i, N - coins[i], expr + " " + coins[i]);
     recursion(coins, i + 1, N, expr);
}

// O(N^2) time complexity
int dynamicProgramming(int[] coins, int N) 
{
     int [] dp = new int[N …

给定一个正整数的二维数组，找到大小为 HxW 且总和最大的子矩形。矩形的总和是该矩形中所有元素的总和。

输入： 具有正元素的 2D 数组 NxN 子矩形的 HxW 大小

输出： 具有最大元素和的 HxW 大小的子矩阵。

我已经使用暴力方法解决了这个问题，但是，我现在正在寻找具有更好复杂性的更好解决方案（我的暴力方法的复杂度是 O(n ⁶ )）。

我正在尝试解决问题并提出一个正确回答的递归关系。代码 ：

 private static int recurse( int[] prices, int index, int[][] dp ) {

    if (index == prices.length - 1) {
        return 0;
    }

    int profit = 0, min = Integer.MAX_VALUE;

    int m = index;
    for (; m < prices.length; m++) {

        min = Math.min(min, prices[m]);//picking at min prices

        int diff = prices[m] - min;//diff. for current min. picked stock profit

        if (dp[m][index] != -1)
            return dp[m][index];

        if (diff > 0) {
            diff += recurse(prices, m + 1, dp);
        } …

我了解两种方法的目标方法，其中最优子结构根据输入 n 计算最优解，而重叠子问题针对输入范围内的所有解，比如从 1 到 n。

对于像杆切割问题这样的问题。在这种情况下，在找到最佳切割时，我们是否考虑每个切割，因此可以将其视为重叠子问题并自下而上地工作。或者我们是否考虑给定输入 n 的最佳切割并自上而下工作。

因此，虽然他们最终确实处理了最优性，但两种方法之间的确切区别是什么。

我尝试参考这个重叠子问题、最优子结构和这个页面。

另外，这是否与制表（自上而下）和记忆（自下而上）的解决方法有关？

这个线程提出了一个有效的观点，但我希望它可以更容易地分解。

这是我的要求，当我单击“添加”按钮时，应生成具有三个 TextField 的动态新卡，以及如何使用动态创建的 TextEditingControllers> 分配每个 TextField，或者是否有其他方法可以从 TextField 中获取值？

final name1 = new TextField(
    controller: name1Controller,
    decoration: InputDecoration(
        labelText: 'Full Name', border: OutlineInputBorder()));

final age1 = new TextField(
    controller: age1Controler,
    keyboardType: TextInputType.number,
    decoration:
        InputDecoration(labelText: 'Age', border: OutlineInputBorder()));

final studyjob1 = new TextField(
    controller: study1Controller,
    decoration: InputDecoration(
        labelText: 'Study / Job', border: OutlineInputBorder()));

final person1Card = new Card(
  shape: RoundedRectangleBorder(
    borderRadius: BorderRadius.circular(15.0),
  ),
  elevation: 10,
  child: Padding(
    padding: EdgeInsets.only(top: 2.0, left: 6.0, right: 6.0, bottom: 2.0),
    child: Column(
      children: <Widget>[
        Text('Person 1'), …

为了使动态规划适用，问题必须具有两个关键属性：最优子结构和重叠子问题 [1]。对于这个问题，我们将只关注后一个属性。

重叠子问题有多种定义，其中两个是：

• 如果问题可以分解为多次重复使用的子问题，或者该问题的递归算法一遍又一遍地解决相同的子问题，而不是总是生成新的子问题 [2]，则称该问题具有重叠的子问题。
• 要应用动态规划，优化问题必须具备的第二个要素是子问题的空间必须“小”，因为该问题的递归算法一遍又一遍地解决相同的子问题，而不是总是生成新的子问题（CLRS算法介绍）

如果找到解决方案涉及多次解决相同的子问题，那么这两个定义（以及互联网上的许多其他定义）似乎都可以归结为具有重叠子问题的问题。换句话说，在寻找原始问题的解决方案的过程中，有许多小的子问题被多次计算。一个经典的例子是斐波那契算法，很多例子都用来让人们理解这个属性。

直到几天前，生活都很棒，直到我发现了Kadane 的算法，这让我质疑重叠的子问题定义。这主要是因为人们对它是否是 DP 算法有不同的看法：

• Kadane 算法中的动态规划方面
• Kadane 的算法是否考虑 DP？以及如何递归地实现它？
• Kadane 的算法是贪心算法还是优化 DP？
• 动态编程与记忆化（见我的评论）

有人不认为 Kadane 的算法是 DP 算法的最令人信服的原因是每个子问题只会在递归实现中出现和计算一次[3]，因此它不包含重叠子问题的属性。然而，互联网上的很多文章都认为 Kadane 的算法是一种 DP 算法，这让我怀疑我对重叠子问题的理解首先意味着什么。

人们似乎对重叠子问题的属性有不同的解释。使用简单的问题（例如斐波那契算法）很容易看到它，但是一旦您介绍了 Kadane 的算法，事情就会变得非常不清楚。如果有人能提供一些进一步的解释，我将不胜感激。

用偶数异或找出子数组的数量（子数组的异或意味着其元素的异或）。例如：

l=[1,2,3,4]   # ----> Answer of this is 4

（解释：[2],[4],[1,2,3],[1,2,3,4]--->这些是异或偶数的子数组，因此子数组数=4）

这是我的代码：

def odd_int(lst):
    odd=0
    for i in lst:
        if i%2!=0:
            odd+=1 
    return odd    
l=list(map(int,input().split()))
x=0 # Denotes number of even xor arrays
for i in range(len(l)):
    for j in range(i,len(l)):
        l1=l[i:j+1]
        y=odd_int(l1)
        if y%2==0:
            x+=1
print(x)

上面的代码超过了时间限制，所以有什么建议可以将它优化为 O(n)？？？谢谢你的时间！！！