标签: dynamic-programming

假设S = 5且N = 3,解决方案看起来像 - <0,0,5> <0,1,4> <0,2,3> <0,3,2> <5,0,0> < 2,3,0> <3,2,0> <1,2,2>等

在一般情况下,N个嵌套循环可用于解决问题.运行N嵌套循环,在它们内部检查循环变量是否加到S.

如果我们提前不知道N,我们可以使用递归解决方案.在每个级别中,运行从0到N的循环,然后再次调用函数本身.当我们达到N的深度时,看看获得的数字是否加起来为S.

其他动态编程解决方案？

在这篇文章中,它将Dijkstras描述为一种贪婪的算法,而在这里和这里它被证明与动态编程算法有联系.

那是哪一个呢？

最近,我在接受采访时被问到以下问题.

给定字符串S,我需要找到另一个字符串S2,使得S2是S的子序列,并且S是S2 +反向的子序列(S2).这里'+'表示连接.我需要为给定的S输出最小可能的S2长度.

我被告知这是一个动态编程问题,但我无法解决它.有人可以帮我解决这个问题吗？

编辑-

有没有办法在O(N ²)或更少的情况下执行此操作.

在一次采访中,我被问到这个问题:给定一些正整数s,找到最长子阵列的长度,使其所有值的总和小于或等于某个正整数k.每个输入始终至少有一个解决方案.该数组不是圆形的.

我开始编写动态编程解决方案,通过在0到k的越来越大的值中找到最大长度来工作.

这是我在python中的代码,里面有一个我似乎无法找到的错误,我的答案总是偏离几位数:

def maxLength(s, k):
    lengths = [0 for x in range(k)]
    for i in range(1,k+1):
        for j in range(len(s)):
            if s[j] <= i and lengths[i - s[j]] + 1 > lengths[i]:
                lengths[i] = lengths[i - s[j]] + 1
        if i + 1 == len(s):
            break
    return lengths[-1]

输入1:s = [1,2,3], k = 4

输出1: 2

输入2: s=[3,1,2,1], k = 4

输出2: 3

如果从连续段中选取相同的数字,则计算最大总和

[1,2,3,4] => answer 6
if 1 is picked from continuous segment [1,1,1,1] then sum is 4 
if 2 is picked from continuous segment [2,3,4] then sum is 6 , 

[6,0,6,5,5,2] => answer 15, continuous segment [6,5,5] , 
5 can be picked from 3 elements.
[1,100,1,1] => answer 100, we can't pick 1 as 1+1+1+1 = 4 <100

除了O(n ^ 2)循环,我想不出任何解决方案

我在接受采访时遇到了以下问题:

给定一个有N个台阶的楼梯,每次可以进行1步或2步.输出从下到上的所有可能方式.

例如:

N = 3

Output :
1 1 1
1 2
2 1

在面试时,我只是说使用动态编程.

S(n)= S(n-1)+1或S(n)= S(n-1)+2

但是,在采访中,我没有为此编写非常好的代码.你会如何编写这个问题的解决方案？

谢谢!

我在互联网上发现了以下问题,并想知道我将如何解决它:

问题:没有重新排列的整数分区

输入:非负数的排列S {s ₁,... ..,s _n }和整数k.

输出:将分区S分成k个或更少的范围,以最小化所有k个或更少范围的总和的最大值,而无需重新排序任何数字.*

请帮忙,看起来像有趣的问题......我实际上花了很多时间,但没有看到任何解决方案..

我在一次采访中向我询问了这个问题,并且令人尴尬地暴露了我在动态编程方面的缺点.如果有人可以帮我解决这个问题,我将不胜感激.此外,如果您能够在设计解决方案时解释您的思维过程对我(以及其他人)非常有帮助,因为当我看到一个使用动态编程范例的解决方案但我很难理解时,我似乎能够理解跟我一起.

不用多说,这是我被问到的问题.

给定一个整数i,并设置X的k点x1,x2,... xk上实线,选择i从设定点X,以尽量减少对距离的每一个点的总和X到一个点在i使用动态规划.

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
   (a) max_ending_here = max_ending_here + a[i]
   (b) if(max_ending_here < 0)
         max_ending_here = 0
   (c) if(max_so_far < max_ending_here)
          max_so_far = max_ending_here
 return max_so_far

我可以帮助我理解上述算法中最佳的子结构和重叠问题(DP的面包和黄油)吗？

这是算法课程简介中的一个问题:

你有一个n个随机正整数的数组(数组不需要排序或元素唯一).建议使用O(n)算法来找到可被n整除的最大元素总和.

使用动态编程在O(n ²)中找到它并使用余数0,1,2,...,n - 1存储最大和是相对容易的.这是一个JavaScript代码:

function sum_mod_n(a)
{
    var n = a.length;

    var b = new Array(n);
    b.fill(-1);

    for (var i = 0; i < n; i++)
    {
        var u = a[i] % n;
        var c = b.slice();

        for (var j = 0; j < n; j++) if (b[j] > -1)
        {
            var v = (u + j) % n;
            if (b[j] + a[i] > b[v]) c[v] = b[j] + …