我有一个背包问题的简单解决方案的代码，我想获取所选项目的索引列表，目前它正在返回所选项目的值的总和。任何帮助将不胜感激。Java代码：
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
/* A Naive recursive implementation of 0-1 Knapsack problem */
class Knapsack
{
// A utility function that returns maximum of two integers
static int max(int a, int b) {
return (a > b)? a : b; }
// Returns the maximum value that can be put in …输入：
listi = [9, 7, 8, 4, 6, 1, 3, 2, 5]
输出：
# m=3
listo = [9, 8, 8, 6, 6, 3, 5]
给定一个由数字组成的随机列表n，我需要找到m连续元素的所有子列表，从子列表中选择最大值并将它们放入一个新列表中。
def convert(listi, m):
listo = []
n = len(listi)
for i in range(n-m+1):
listo.append(max(listi[i:3+i]))
return listo
这个实现的时间复杂度是O(m\^{(n-m+1)}，如果很长的话就很糟糕了listi，有没有办法以 的复杂度来实现这个O(n)？
当返回命令有两个递归调用（例如 ）时
return fib(n-1) + fib(n-2);，这两个调用是同时执行，还是fib(n-1)先于 执行fib(n-2)？
fib(n-1)通过使用记忆，时间复杂度降低到 O(n)，但是只有在之前执行fib(n-2)（然后使用存储的值）才可能吗？
*public int fib(int n)是一种使用递归计算第 N 个斐波那契数的方法。
有N个楼梯，站在底部的人想要到达顶部。该人一次可以爬 1 个楼梯或 2 个楼梯。数数方式，此人可登顶（顺序无所谓）。注意：顺序无关紧要意味着对于 n=4 {1 2 1},{2 1 1},{1 1 2} 被认为是相同的。
https://practice.geeksforgeeks.org/problems/count-ways-to-nth-stairorder-does-not-matter/0
所以我一直在尝试解决这个问题，我面临的问题是我不明白我们如何解决这些顺序无关紧要的问题？当订单很重要时，我能够解决这个问题，但我无法开发解决这个问题的逻辑。
这是我在订单重要时编写的代码
long int countWaysToStair(long int N)
{
if(N == 1 || N == 2)
return N;
long int dp[N+1];
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for(int i=3;i<=N;i++)
{
dp[i] = dp[i-1] + dp[i-2];
}
return dp[N];
}
输入：4 预期输出：3 我的输出：5
我在互联网上读过两个不同的问题0-1背包问题和无界背包问题。我发现这两个问题都可以通过动态规划来解决，但是以两种不同的方式。如果0-1背包问题使用二维数组来解决，无界背包问题只使用一维数组。
据我所知，这两个问题的区别在于，0-1 背包问题只包含有限数量的东西，而无界背包问题可以获取任何资源的 1 个或多个实例。但是，我不知道为什么要改变解决这个问题的方式？你能告诉我原因吗？
给定一个数n和整数k，检查 k 个素数的和是否为n。
input 13 2
output: yes
explanation: 11+2 equals 13
由于 k 被假定为任何一般整数，我不知道如何解决它。我想通过创建所有质数的集合并寻找 k 数来解决它，但即使 k 小到 5，我们也必须运行 4 到 5 次循环才能做到这一点。如何解决此类问题，请寻求帮助，谢谢。我尝试初始代码为：
#include<iostream>
#include<unordered_set>
#include<vector>
using namespace std;
bool is_prime(int n){
bool flag =true;
for(int i=2;i<n;i++){
if(n%i==0 && n!=i){
flag=false;
break;
}
}
if(flag){
return true;
}
return false;
}
int main(){
int n;cin>>n;
int k;cin>>k;
unordered_set<int>s;
for(int i=2;i<n;i++){
if(is_prime(i)){
s.insert(i);
}
}
}
我正在尝试解决找到最小数量的完美平方（即1、2、4、9..）的问题，其总和为n
这是我的自上而下的递归方法：
import math
class Solution:
def numSquares(self, n: int) -> int:
dp = [math.inf] * (n + 1)
dp[0] = 0
dp[1] = 1
def solve(n: int):
if dp[n] != math.inf:
return dp[n]
for i in range(n, 0, -1):
if n - i * i >= 0:
sol = solve(n - i*i)
dp[i] = min(1 + sol, dp[i])
return dp[n]
solve(n)
print(dp)
Solution().numSquares(12)
我无法弄清楚为什么这段代码不能产生正确的结果。你能帮我找到这个错误吗？
谢谢！
我正在尝试在 Haskell 中编写“如何使用最少的硬币amount来访问各种面额的硬币”功能。coins我用 DFS 实现了这个，它可以工作，但速度太慢了。在Python（我的主要语言）中，我可以记住结果并让相同的算法运行得非常快。我尝试在 Haskell 中做同样的事情，但收效甚微。
我将给出一个问题的玩具版本，我试图理解记忆化，然后向 DFS 展示我实际上试图记忆化的情况。
玩具问题
从Haskell Wiki 的 memoization 页面来看，实现此目的的一种方法是索引到无限列表中。类似的要点。
memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
where fib 0 = 0
fib 1 = 1
fib n = memoized_fib (n-2) + memoized_fib (n-1)
这对我来说很有意义——常规递归关系调用记忆列表的索引，如果有的话，它会给出值，并且可以回退到辅助函数。：竖起大拇指：
一个小的修改就打破了这个：
memoized_fib :: Int -> Integer
memoized_fib n = (map fib [0 ..] !! n) -- now no longer lazily evaled!
where fib 0 = 0 …输入：二维点数组 ((x, y), (x2, y2), ...)
输出：最大可能矩形的区域，其 4 个角为给定点中的 4 个点。
注意：矩形不必平行于任何轴，至少可以用一组点制作一个矩形
示例 1：
输入：[[1,2], [2,1], [1,0], [0,1]]
输出：2
解释：
矩形在 2d 平面上如下所示：
2 x
1 x x
0 x
0 1 2
每条边长均为 sqrt(2)，因此面积为 2。
示例 2：
输入：[[0,1], [2,1], [1,1], [1,0], [2,0]]
输出：1
说明：
飞机：
2
1 x x x
0 x x
0 1 2
唯一可能的矩形是边长为 1 的正方形，因此面积为 1。
我将不胜感激任何解决这个问题的帮助，老实说我不知道如何提高效率。有可能吗？
我尝试了暴力破解，即检查 4 个点的所有可能组合，看看它们是否形成一个矩形，然后比较它们的面积，但对于大输入来说太慢了......
这是另一个动态编程问题,在给定矩阵中找到最大L(象棋马 - 4项)总和(mxn)
例如 :
1 2 3
4 5 6
7 8 9
L:(1,2,3,6),(1,4,5,6),(1,2,5,8),(4,5,6,9)......
最大的和是sum(L)= sum(7,8,9,6)= 30
什么是最优解的O(复杂性)？
它看起来像这个问题(具有最大总和的子矩阵)
说所有项目都是积极的
积极和消极
欢迎任何想法!