标签: dynamic-programming

我想在页面加载事件上创建一个 div 元素，但我的脚本未按预期工作。

function createfn(){
    //debugger;
    var element = document.createElement("div");
    var para = document.createTextNode('The man who mistook his wife for a hat');
    element.appendChild(para);
    document.getElementByTagName(body).appendChild(element);
    
}
window.onload=createfn();

这段代码有什么问题？

s这是使用自下而上动态规划查找给定字符串的最长回文子串的算法。因此，该算法会探索所有可能长度的子串，并检查它是否是1 到 n 中的j有效回文。j由此产生的时间和空间复杂度为O(n^2)。

def longestPalindrome(s):
    n = len(s)
    if n < 2:
        return s
    P = [[False for _ in range(n)] for _ in range(n)]
    longest = s[0]

    # j is the length of palindrome
    for j in range(1, n+1):
        for i in range(n-j+1):
            # if length is less than 3, checking s[i] == s[i+j-1] is sufficient
            P[i][i+j-1] = s[i] == s[i+j-1] and (j < 3 or P[i+1][i+j-2])
            if P[i][i+j-1] and j …

我正在尝试获得目标金额总和的所有硬币。我能够获得所需数量的硬币。我将如何解决它。

您可以无限地使用相同的硬币，例如。change([2], 10)=>[2, 2, 2, 2, 2]

def change(coins, amount):
    result = [amount+1] * (amount+1)

    result[0] = 0

    for i in range(1, amount+1):
        for coin in coins:
            if i >= coin:
                result[i] = min(result[i], result[i-coin] + 1)

    if result[amount] == amount+1:
        return -1

    return result[amount]

change([1, 2, 5,8], 7)=>[5, 2]顺序并不重要。

示例：给定 Total = 8 且 k = 2，将 8 表示为 1 到 2（含）之间的整数之和的不同方式有 5 种：

[1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 2]
[1, 1, 1, 1, 2, 2]
[1, 1, 2, 2, 2]
[2, 2, 2, 2]

限制条件：

1 <= total <= 1000
i <= k <= 100

我们该如何解决这个问题呢？动态规划？

问题 - 假设您有一个数组，其ith元素是给定股票在 day 的价格i。

如果您最多只被允许完成一笔交易（即买入一股并卖出一股股票），请设计一种算法来找到最大利润。

请注意，您不能在购买股票之前出售股票。

示例1：

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

示例2：

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

我相信这个问题可以使用动态编程来解决，在简单地继续解决方案之前，我尝试使用我自己的方法来解决这个问题。我确实检查了蛮力算法并意识到我的方法与蛮力并不相似

public class Solution {
    public int maxProfit(int prices[]) {
        int …

我是 Haskell 的新手，并且一直在通过做一些简单的编程挑战来练习。最近两天，我一直在尝试在这里实现无界背包问题。维基百科页面上描述了我使用的算法，但对于这个问题，“重量”一词被替换为“长度”一词。无论如何，我开始编写没有记忆的代码：

maxValue :: [(Int,Int)] -> Int -> Int
maxValue [] len = 0
maxValue ((l, val): other) len =
    if l > len then 
        skipValue
    else 
        max skipValue takeValue
    where skipValue = maxValue other len
          takeValue = (val + maxValue ([(l, val)] ++ other) (len - l)

我曾希望 haskell 会很好，并且有一些很好的语法#pragma memoize来帮助我，但是四处寻找示例，解决方案是用这个斐波那契问题代码解释的。

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
   where fib 0 = …

我是一名计算机科学工程专业的学生，​​我在许多任务中都遇到了这个问题。

我得到了一个大小的数组有价值观然后问了一些问题。

在每个查询中我都会得到两个索引在哪里。

我相信，有一种方法可以回答这个问题如果进行了一些预处理。

我必须这样做。

我已经解决这个问题很多天了，但我根本无法解决。

在我尝试学习 Haskell 的过程中，我编写了以下代码来解决一个经典的优化问题。当前的问题是计算销售最大化价格，其中价格单调递增，给定 i 个买家序列，每个买家将以 v_i 的最大价格购买。用数学术语来说：给定 [v_i] ，找到 [p_i] st p_{i+1} >= p_i 最大化 \sum_i q(v_i,p_i) 其中 q(a,b)=0，如果 b>a, q( a,b)=b b<=a

我已经实现了以下代码，使用我认为的自上而下的动态编程方法来解决问题。该算法在每一步都通过最大化剩余序列来决定是否提高价格

maxP::Int->[Int]->(Int,Int)
maxP p [] = (0,p)
maxP p q 
   | a<p = (fst (maxP p (tail q)),p)
   | a==p = (p+fst (maxP p (tail q)),p)
   | otherwise =(maximum l,p+argmax l)
     where a=head q
           pc=[p..a]
           l=zipWith (+) pc $ map (fst)  ( map ((flip maxP) (tail q)) pc )

正如使用 Haskell 时所预期的那样，该代码几乎是 DP 算法的 1-1 实现。该代码返回（销售额，价格水平）

并且，为了获得所有价格序列，为所有 …

我最近在一次在线评估中遇到了这个问题。

arr = [2,6,2,4] 
k = 15

仅当两个相邻元素的乘积小于 时，才需要通过相乘来最小化数组元素k。

例子：

(2,6,2,4)
(2*6,2*4) --> since 12 and 8 are less than k which is 15
(12,8)

还可以遵循以下模式：

(2,6,2,4)
(2,6*2,4) 
(2,12,4) --> no . of  elements is 3 which is more than 2 thus non-optimal.

我已经被这个问题困扰好几天了。

我尝试解决矩阵链乘法问题，但无法取得任何进展。主要区别在于，在 MCM 问题中，所有矩阵都可以相互相乘。不存在两个矩阵不能相乘的情况。

有什么提示吗？

str我在范围内有一串小写字母[a-z]。字符串中的几个字母组合在一起时代表一个数字，[0-9]即“零”= 0、“一”= 1、“二”= 2 等等。

字符串中的字符混乱。但是，保证字符串中的所有字符都可以用来组成一组数字。有些数字也可以重复。不存在a、p等无效字符q。

我的任务是求 所代表的数字之和str。

示例 :
str= "oneeno" 应输出2 (1+1)
str= "onewtofoursevne" 应输出14 (1+2+4+7)

让solve(s)表示求解 的特定子串str。
我有一个字符串数组，v用于存储数字的拼写。v = {“零”，“一”，“二”，...“九”}；

s只要我能找到代表数字的一组字符，我就会分解并添加数字值。

if (contains(s, v[i]) == true)
    dp[s-v[i]] = i + solve(s-v[i])

s-v[i]v[i]表示从 中删除的字符集s。由于不可能以这种方式减去字符串，因此我s-v[i]用change(s, v[i])（在我的代码中）替换。

这看起来像是一个具有多个重复子状态的递归函数。
例如 ：solve(s - v[1] - v[4] - v[7]) = …