我目前正在解决以下问题:

给定一个M个正数的数组,我需要得到N个具有一定长度的连续数字块.例如,当我有数组时:

6 9 3 2 8 1 6 9 7

当我需要找到一个长度为3的块时,解决方案是[3,2,8],它的最小总和为13.当我需要找到两个块时,算法应该给出[3,2,8]和[1,6,9]因为这些块中所有元素的总和是最小的(29).假设序列的长度总是严格大于块长度的N倍(因此始终存在解决方案).

我认为这个问题可以通过使用DP解决,但我目前看不出如何.我很难找到子问题之间的经常性关系.有人能帮我一把吗？

提前致谢!

我有一个奇怪的问题.我在C++中有以下代码:

int grid[h][w]; int dp[h][w]; int p[h][w];

for(int y = 0; y < h; y++)
    for(int x = 0; x < w; x++)
        cin >> grid[y][x];

// base case
for(int y = 0; y < h; y++) dp[y][0] = grid[y][0];


// fill rest
for(int x = 1; x < w; x++)
{
    for(int y = 0; y < h; y++)
    {
        dp[y][x] = min(dp[y][x-1], min(dp[(y-1)%h][x-1], dp[(y+1)%h][x-1])) + grid[y][x];
    }
}

cout << "dp: " << endl;
for(int y = 0; …

看看下面的代码,我用两种方法来解决问题(简单的递归和DP).为什么DP方式更慢？

你的建议是什么？

#!/usr/local/bin/python2.7
# encoding: utf-8

问题:有一个带正整数的数组.给定正整数S,\找到数字和为S的组合总数.

方法一:

def find_sum_recursive(number_list, sum_to_find):
    count = 0

    for i in range(len(number_list)):        
        sub_sum = sum_to_find - number_list[i]
        if sub_sum < 0:
            continue
        elif sub_sum == 0:
            count += 1
            continue
        else:            
            sub_list = number_list[i + 1:]            
            count += find_sum_recursive(sub_list, sub_sum)       
    return count

方法二:

def find_sum_DP(number_list, sum_to_find):
    count = 0

    if(0 == sum_to_find):
        count = 1
    elif([] != number_list and sum_to_find > 0):   
        count = find_sum_DP(number_list[:-1], sum_to_find) + find_sum_DP(number_list[:-1], sum_to_find - number_list[:].pop())     

    return count

运行它: …

给我一个很大的数字n,我需要找到它是否可以表示为K素数的总和.

Ex 9可以表示为3素数之和为2 + 2 + 5.

我试图使用子集和的变化,但数量太大,无法生成所有素数.

问题来自当前的HackerRank比赛.限制是1 <= n, K <= 10^12

我使用动态编程技术编写了以下代码,但是当我运行Fibonacci为220时,我得到一个负数.这个程序有错吗？

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Fibonaci {

    public static void main(String[] args) {
        System.out.println(" number ");
        long startTime = System.currentTimeMillis();
        HashMap<Integer, Integer> memoized = new HashMap<Integer, Integer>();
        int fib = fibonanci(220, memoized);
        System.out.println(" Total Time "
                + (System.currentTimeMillis() - startTime));

    }

    private static int fibonanci(int n, HashMap<Integer, Integer> memoized) {
        System.out.println(" n " + n);
        if (memoized.containsKey(n)) {
            return memoized.get(n);
        }

        if (n <= 0) {
            return 0;
        }
        if (n <= 2) {
            return 1; …

动态规划问题具有最优子结构,并且具有可以通过递归关系描述的解决方案.

排序列表是向已排序列表添加元素,因此插入排序具有最佳子结构.递归关系可以描述为

Sorted_List_n = Sorted_list_n-1 + next element

那么为什么插入排序不被认为是动态编程算法呢？我理解它是如何应用于斐波纳契数和编辑距离的,但并不是真的超出了它.

我正在研究用Python 制作硬币问题的经典改造.这是我的实施.

def memo(fn):
    def helper(*args): # here, * indicate the fn take arbitrary number of argumetns
        d = {}
        if args in d:
            return d[args] # args is a tuple, immutable, hashable
        else:
            res = fn(*args) # here * expand a tuple as arguments
            d[args] = res
            return res
    return helper

@memo
def change(options, n):
    if n < 0 or options ==():
        return 0
    elif n == 0:
        return 1
    else:
        return change(options, n- options[0]) + change(options[1:], n) …

是否可以在Haskell中创建一个函数,该函数返回数据类型的构造函数列表？

它应该像这样工作:

ghci> getConstructors Bool
[True, False]
ghci> getConstructors Maybe
[Nothing, Just]

问题:

你给出的阵列米大小的Ñ,其中的每个值米由重量的瓦特和百分比p.

m = [m0, m1, m2, ... , mn] = [[m0w, m0p], [m1w, m1p], [m2w, m2p], ..., [mnw, mnp] ]

所以我们将在python中将其表示为列表列表.

然后我们试图找到这个函数的最小值:

def minimize_me(m):
    t = 0
    w = 1
    for i in range(len(m)):
        current = m[i] …

假设我们有一个带有n个元素的数组(n%3 = 0).在每个步骤中,从数组中取一个数字.你要么是最左边的,要么是最右边的.如果选择左边的元素,则将此元素添加到总和中,并删除右边的两个数字,反之亦然.

示例:A = [100,4,2,150,1,1],sum = 0.

1. 采取最左边的元素.A = [4,2,150] sum = 0 + 100 = 100

2.采取最右边的元素.A = [] sum = 100 + 150 = 250

所以A的结果应该是250,序列是Left,Right.

如何计算数组中可以得到的最大总和？我如何确定我必须提取元素的顺序？

我想这个问题最好用动态编程来解决,然后可以通过回溯来确定具体的顺序.