标签: dynamic-programming

我有以下递归函数:

typedef unsigned long long ull;

ull calc(ull b, ull e)
{
  if (!b) return e;
  if (!e) return b;
  return calc(b - 1, e - 1) + calc(b - 1, e) - calc(b, e - 1);
}

我想用动态编程(即使用存储)来实现它.我试过用a map<pair<ull, ull>, ull>但它也太慢了.我也无法使用数组实现它O(1).

我想找到一个解决方案,以便此函数可以快速解决大b, es问题.

也许我误解了这个问题.对于那些不熟悉Project Euler问题31的人来说,问题是:

调查英国货币面额的组合.

在英格兰,货币由英镑,英镑和便士p组成,一般流通中有八个硬币:

1p,2p,5p,10p,20p,50p,£1(100p)和£2(200p).

可以通过以下方式赚取2英镑:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

使用任意数量的硬币可以制作多少种不同的方式？

我看到这可能是一个动态编程问题,但我忍不住走捷径:

为了解决这个问题,我分解了使用1p,1p和2p以及1p,2p和5p硬币可以制造1到6便士的方法.

仅使用一分钱硬币

1. 1组合
   • 1P
2. 1组合
   • 2×1P
3. 1组合
   • 3×1P
4. 1组合
   • 4×1P
5. 1组合
   • 5×1P
6. 1组合
   • 6×1P

仅使用一便士和两便士硬币

1. 1组合
   • 1P
2. 2种组合
   • 2P
   • 2×1P
3. 2种组合
   • 2p + 1p
   • 3×1P
4. 3种组合
   • 2×2P
   • 2p + 2×1p
   • 4×1P
5. 3种组合
   • 2×2p + 1p
   • 2p + 3×1p
   • 5×1P
6. 4种组合
   • 3×2P
   • 2×2p + 2×1p
   • 2p + 4×2p
   • 6×2P

仅使用一便士,两便士和五便士硬币

1. 1种组合
   • 1P
2. 2种组合
   • 2P
   • 2×1P
3. 2种组合
   • 2p + 1p
   • 3×1P …

我遇到了以下动态编程问题.

你有一个整数网格(所以包括负数).找到具有最大数字总和的矩形.

知道如何为整个矩阵做到这一点吗？

我为一个阵列解决了这个问题,所以我几乎遵循了增长最快的子程序,但仅限于连续数字.

def array_largest_block(sequence)
  len = sequence.size
  parents = [nil]*len
  my_largest = sequence
  largest = sequence.max

  for index in (1...len)
    if my_largest[index] < my_largest[index] + my_largest[index - 1]
      my_largest[index] = my_largest[index] + my_largest[index - 1]
      parents[index] = index - 1
      largest = [largest, my_largest[index]].max
    end
  end

  end_index_of_largest_block = my_largest.find_index(largest)
  i = end_index_of_largest_block
  res = []
  res << sequence[i]
  while !parents[i].nil?
    i = parents[i]
    res << sequence[i]
  end
  return {l_sum: largest, start: i, end: end_index_of_largest_block}
end

所以我的想法是,

1. 找到矩阵中每个方格的总和(仅1x1个方块)
2. 为可能的答案保存最大值 …

我最近发现了一种叫做动态编程的技术,我偶然发现了一个我无法弄清楚的问题.您在开头就会得到一个参数列表,您需要对它进行总结,就像您正在削减它一样.如果列表只有一个元素,则不要求它.如果它有更多,你总结元素并以各种可能的方式切割它.因此,如果list有n个元素,那么只有n-1种方法可以删除它.图片将解释:

我首先要总结所有可用的部分,我期望结果20(11 + 9)(甚至认为正确的答案是9),但我认为这将是一个良好的开端.但我的代码返回37号,我不知道为什么.我究竟做错了什么？

summ = 0

def Opt( n ):
    global summ

    if len( n ) == 1:
        return 0
    else:
        summ += sum( n )
        for i in range( 1,len( n ) ):
            summ += Opt( n[ :i ] ) + Opt( n[ i: ] )

        return summ

print( Opt( [ 1,2,3 ] ) )

感谢您的时间和任何答案!

我们如何开发一种动态编程算法来计算总和的最小不同素数x？

假设动态编程计算不同质数的最小数量,其中最大数量p为每个x和p.有人可以帮忙吗？

我最近接受了一个实习职位的面试，其中一个问题与此类似：

输入：n表示动作次数，k表示您无法踩到的楼梯

问题：杰克有n个动作要达到最大步数，但不能踩第k阶。对于每一个动作，杰克都可以停留在当前位置，也可以跳至第i步（如果他正在进行第i个动作），并且一直持续到完成第n个动作为止。

输出：n次动作内可达到的最大楼梯

它通过Hackerrank（与面试官在一起）进行了测试，在8个测试用例中，我仅通过了3个，其余时间超时

这是我的解决方案，它是即时进行编码的，我无法对其进行优化，并且想知道是否存在更加优化的解决方案：

static int maxStep(int n, int k) {
    int result = 0;
    if (n == 0) {
        return result;
    } 
    return maxStepHelper(n,0, k, result);
}

static int maxStepHelper(int n,int i,int k,int result) {
    // At n+1 steps, previous steps' results are recorded and this is mainly used to stop and show previous results
    if (i == n+1) {
        return result;
    }
    int nextStep = i + result;
    if (nextStep == k) { …

我有一个动态的编程问题,我花了几个小时研究无济于事.

第一部分很简单:你有一个背包物品,你必须最大化这些物品的价值,同时保持低于一定的重量.

问题的第二部分是相同的,除了现在还有一个项目限制.例如:

您可以放入包中的物品的最大价值是什么,以便在重量和物品限制的情况下最大化价值？

我不知道如何实现这个问题的第二部分,我正在寻找一般的算法.

我试图在codeforces上解决问题811C.我开始编写sublime-text编码,并设法在一段时间后提出解决方案.当我运行该程序时,它给了我正确的答案但是当我提交代码时,出于某种原因我得到了代码强制的不同答案.我检查了数组是否超出范围,但这似乎不是原因.这是代码:

/* Code Readability Credit : Max Vollmer */
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <set>

// terms[] stores the value of all the terms. leftMosts[i] and rightMosts[i] store the leftmost and rightmost occurrences of the ith element in terms[]. 
//solvedValues[] stands for dynamic programming and stores the pre calculated terms of the function solve()
int numberOfTerms;
int terms[5005];
int leftMosts[5005];
int rightMosts[5005];
int solvedValues[5005];

int comf(int left,int right)// comf = …

我需要打印出数字N可以表示为1,3,4之和的不同方式。

例如n = 5：

• 1 +1 +1 +1 +1
• 1 + 4
• 4 + 1
• 1 + 1 + 3
• 1 + 3 + 1
• 3 +1 +1

我正在使用动态编程解决方案来查找n可以写为1,3,4之和的可能方式的数量

    for i in range(4, n + 1): 
        DP[i] = DP[i - 1] + DP[i - 3] + DP[i - 4] 

    return DP[n]

可行，我得到了可以表达N的可能方法的数量，在这种情况下为6，但是我不确定如何打印出所有不同的方法：

• 1 +1 +1 +1 +1
• 1 + 4
• 4 + 1
• 1 + 1 + 3
• 1 + 3 + 1
• 3 +1 +1

任何建议都值得欢迎，谢谢！

我们必须在给定的字符串中找到散文回文字符串，并在字符串中返回散文回文数。例如，给定字符串“ aabb”，分散回文式为a，aa，aab，aabb，a，abb，b，bb和b。这里有9个散点回文的子字符串。

我曾考虑过蛮力方法，即生成所有子字符串并检查它们，但我想找到一种更好的方法。