我正在寻找以下问题的答案。

给定一组整数（无重复）和一个总和，找到该组元素的所有可能组合，总和为总和。解的顺序并不重要（解 {2, 2, 3} 和 {3, 2 ,2} 相等）。

请注意，最终组合不需要是一个集合，因为它可以包含重复项。

示例：设置 {2,3,5} 和 10

结果：{2, 2, 2, 2, 2}, {2, 2, 3, 3}, {2, 3, 5}, {5, 5}

我研究过子集和问题以及硬币找零问题，但无法调整它们以满足我的需要。我不太熟悉动态编程，所以它可能是可行的，但我无法弄清楚。

由于我正在处理相当大的元素集（大约 50 个），因此预先计算所有元素集不是一个选项，因为这会花费很长时间。从子集和表中提取不同解决方案的方法将是更好的方法（如果可能的话）。

任何建议、提示或示例代码将不胜感激！

我有两个非负整数 x 和 y，它们都最多有 30 位（所以它们的值约为 10^9）。

我想计算有多少组 4 个数字 {a_1, a_2, a_3, a_4} 使得 a_1 + a_2 = x 和 a_3 + a_4 = y 并且所有这 4 个数字的异或等于 0。

解决这个问题最快的算法是什么？

我能想到的最快的方法是将异或方程重新排列为a_1 xor a_2 = a_3 xor a_4。

然后我可以在 O(x) 中计算左侧的所有值，在 O(y) 中计算右侧的所有值，因此整个算法在 O(x + y) 中运行。

这就是问题所在：给定块数 n（3 到 200 之间），返回可以建造的不同楼梯的数量。每种类型的楼梯应包含 2 个或更多台阶。不允许有两个台阶处于相同高度 - 每个台阶必须低于前一个台阶。所有台阶必须至少包含一块砖块。台阶的高度被分类为组成该台阶的砖块的总数。

例如，当N = 3时，您只有1种选择如何建造楼梯，第一步的高度为2，第二步的高度为1：（#表示一块砖）

#
## 
21

当 N = 4 时，你仍然只有 1 个楼梯选择：

#
#
##
31

但是当 N = 5 时，有两种方法可以用给定的砖块建造楼梯。两个楼梯的高度可以为 (4, 1) 或 (3, 2)，如下所示：

#
#
#
##
41

#
##
##
32

我在网上找到了解决方案，但是我不太直观地理解动态规划的解决方案。

public class Answer {

    static int[][] p = new int[201][201];

    public static void fillP() {
        p[1][1] = 1;
        p[2][2] = 1;

        for (int w = 3; w < 201 ; w++) {
            for (int …

我一直在研究这个问题。

• 目标是用砖建造楼梯
• 有 N 块砖，必须全部用来建造楼梯
• 楼梯由不同尺寸的台阶按严格递增的顺序组成
• 楼梯间不允许有相同尺寸的台阶
• 每个楼梯至少由两个台阶组成，每个台阶至少包含一块砖

完整问题的链接http://acm.timus.ru/problem.aspx?num=1017&locale=en

我已经知道这是处理不同的分区和数论/背包问题。目标是有效地给出一个列表 n = [1,2,3,....n -1] 确定存在多少个加起来为 N 的无序集合。我说无序是因为给定的列表没有重复项，因此任何组合都可以排序为给定大小的有效特定答案以符合规则。我也理解一般概念是你从高度 1 开始并分支/添加所有可能的组合，直到新的高度超过砖块，并且仅当新高度用完所有剩余的砖块时才添加到总组合中那一点。我意识到有一些模式，就像您在进入 4 时已经知道 n = 3 存在多少个分区一样，因此使用该数据（动态编程）是解决方案的一部分。

我最终找到了以下解决方案。

n = int(input())
m = [[0 for i in range(n + 1)] for j in range(n + 1)]
m[0][0] = 1  # base case

for last in range(1, n + 1):
    for left in range(0, n + 1):
        m[last][left] = m[last - 1][left]
        if left >= last:
            m[last][left] += m[last - 1][left - …

这是完整的问题陈述：

给定长度为 n 的绳子，您需要找到
可以制作的最大绳子数，使得对于
给定的三个值 a、b、c，每根绳子的长度都在集合 {a, b, c } 中

我知道可以通过动态规划来实现最优解，但是，我还没有学过这个主题，我需要递归地解决这个问题。对于递归，主要的事情是确定子问题，而这正是我主要遇到的困难。谁能给我一个直观的方式来思考这个问题？如果有意义的话，有点像递归的更高层次的描述。有没有与此类似的更简单的问题我可以先尝试来帮助我解决这个问题？

提前致谢。

Hii 是 javascript 新手，但通过我的全部努力，我编写了一个 javascript 来复制<p></p>元素内的文本。在我的网站中，我多次需要复制按钮。但我的 javascript 仅适用于一个复制按钮。如果我将它用于另一个复制按钮，它将复制第一个按钮的相应<p>/p>文本。我的 JavaScript

const copyButton = document.querySelector('.copyButton');
const copyalert = document.querySelector('.copyalert');

copyButton.addEventListener('click', copyClipboard);

function copyClipboard() {
  var copystatus= document.getElementById("randomstatus");
// for Internet Explorer

  if(document.body.createTextRange) {
    var range = document.body.createTextRange();
    range.moveToElementText(copystatus);
    range.select();
    document.execCommand("Copy");
    window.getSelection().removeAllRanges();
    copyalert.classList.add("show");
    setTimeout(function() {copyalert.classList.remove("show")},700);
  }
  else if(window.getSelection) {
// other browsers

    var selection = window.getSelection();
    var range = document.createRange();
    range.selectNodeContents(copystatus);
    selection.removeAllRanges();
    selection.addRange(range);
    document.execCommand("Copy");
    window.getSelection().removeAllRanges();
    copyalert.classList.add("show");
    setTimeout(function() {copyalert.classList.remove("show")},700);
  }
}

我的网页

<div>
   <h2 class="statusheading">Latest English quotes</h2>
  <div id="englishquotes">
   <div …

我一直在解决算法问题，对这些术语有点困惑。

当我们像下面的代码一样想要计算前缀和（或累积和）时，我们可以说我们正在使用动态规划吗？

def calc_prefix_sum(nums):
    N = len(nums)
    prefix_sum = [0] * (N + 1)
    for i in range(1, N + 1):
        prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1]
    return prefix_sum

nums = [1, 3, 0, -2, 1]
print(calc_prefix_sum(nums))

[0, 1, 4, 4, 2, 3]

根据本页的定义，

动态规划用于遇到问题的地方，可以将问题分成相似的子问题，以便可以重复使用它们的结果。

在我的 prefix_sum 算法中，当前的计算（prefix_sum[i]）被分成类似的子问题（prefix_sum[i - 1] + nums[i - 1]），这样之前的结果（prefix_sum[i - 1]）就可以被重新使用。所以我假设计算前缀和是动态规划的应用之一。

我可以说这是动态规划，还是应该使用不同的术语？（特别是，我正在考虑编码面试中的情况。）

除了 LRU 缓存的结构之外，我还没有读过太多关于它的内容，但我仍然对它比常规哈希图快得多感到惊讶。

我做了一个测试，一个递归组合问题，使用常规哈希图来保存递归期间的结果结果（动态编程），并做了相同的操作，唯一的区别是使用了 LRU 缓存实现（大小 1024）。

性能从1秒下降到0.006秒！

现在，这非常令人惊讶，我不知道为什么会这样。对于大多数操作来说，哈希图的时间复杂度为 O(1)，并且 LRU 缓存需要哈希图和双向链表。

语境：

• 我在这个项目中使用 C++。所讨论的 hashmap 是一个 unordered_map，以字符串作为键，以整数作为值。我听说过 unordered_map 最坏情况的复杂度为N或N ²，但据我所知，它通常在O(1)中执行所有操作。

• LRU 缓存实现是从堆栈溢出复制粘贴的：D

代码

使用 LRU 缓存

#include <bits/stdc++.h>

using namespace std;
using namespace std::chrono;

template <typename T,typename U>                                                   
std::pair<T,U> operator+(const std::pair<T,U> & l,const std::pair<T,U> & r) {   
    return {l.first+r.first,l.second+r.second};                                    
}
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")


// LRU Cache implementation
template <class KEY_T, class VAL_T> class LRUCache{ …

你有一堆n个盒子,宽度为wi,高度为hi,深度为di.如果堆叠中的每个盒子的宽度,高度和深度都大于或等于其上方的盒子,则盒子不能旋转并且只能堆叠在一起.实现一种方法来构建最高的堆栈,其中堆栈的高度是每个盒子高度的总和.

我知道有几篇文章要讨论使用动态编程来解决它.由于我想编写递归代码,我编写了以下代码:

const int not_possible = 999999;

class box{
public:
    int width;
    int depth;
    int height;
    box(int h=not_possible, int d=not_possible, int w=not_possible):
        width(w), depth(d), height(h) {}
};


bool check_legal(box lower, box upper){
    return (upper.depth<lower.depth) && 
           (upper.height<lower.height) &&
           (upper.width<lower.width);
}

void highest_stack(const vector<box>& boxes, bool* used, box cur_level, int num_boxes, int height, int& max_height)
{
    if(boxes.empty())
        return;

    bool no_suitable = true;
    for(int i = 0; i < num_boxes; ++i){
        box cur;
        if(!(*(used+i)) && check_legal(cur_level, boxes[i])){
            no_suitable = false;
            cur = boxes[i]; …

LCS的并行计算遵循波前模式.这是并行函数,它比串行实现慢.(我认为对角线(平行)与行数(串行)的数量与它有关)

void parallelLCS(char * sequence_a, char * sequence_b, size_t size_a, size_t size_b) {
double start, end;

int ** dp_table = new int*[size_a + 1];

for (int i = 0; i <= size_a; i++)
    dp_table[i] = new int[size_b + 1];

for (int i = 1; i <= size_a; i++)
    dp_table[i][0] = 0;
for (int j = 0; j <= size_b; j++)
    dp_table[0][j] = 0;

int p_threads = 2;
int diagonals = size_a + size_b;

start = omp_get_wtime();
#pragma omp parallel num_threads(p_threads) …