标签: dynamic-programming

这是本书的一段：算法导论，第三版。第336页

“这两种方法产生的算法具有相同的渐近运行时间，但在特殊情况下，自上而下的方法实际上不会递归地检查所有可能的子问题。自下而上的方法通常具有更好的常数因子，因为它的开销更少用于过程调用。”

背景：两种方法是第一种是自上而下+记忆（DP），第二种是自下而上的方法。

我还有一个问题要问你。函数调用的“开销”是否意味着每个函数调用都需要时间？即使我们解决了所有子问题，自上而下也会因为“开销”而花费更多时间？

给定n个数，找到最小子集数，其中剩余数等于0。例如：

{1,1,3,4,5}

结果等于 3，因为我们可以删除子集 {1,3}（有两种方式）或 {3,4,5}。

我正在寻找比 O(2^n) 蛮力更快的东西。

我正在尝试进行动态编程以查找 LCS 的长度。我为此使用了二维数组。但是对于大字符串，它会由于内存溢出而导致运行时错误。请告诉我我应该如何在一维数组中做到这一点以避免内存限制。

#include<bits/stdc++.h>
 #include<string.h> 
 using namespace std;
int max(int a, int b);
int lcs( string X, string Y, int m, int n )
{
   int L[m+1][n+1];
   int i, j;
   for (i=0; i<=m; i++)
   {
     for (j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;

       else if (X[i-1] == Y[j-1])
         L[i][j] = L[i-1][j-1] + 1;

       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }

   return L[m][n];
}

int max(int a, int b)
{
    return (a > …

查找在该月的已知日期(1 ... 30)购买旅行所需的最低票价.提供三种类型的门票:1天有效期为1天,2天有效,7天有效7天,7天,30天有效30天,25个单位.

例如:我想在一个月的[1,4,6,7,28,30]天旅行,即每月的第1天,第4天,第6天.......如何购买门票,使成本最低.

我尝试使用动态编程来解决这个问题,但解决方案并没有给我所有案例的正确答案.这是我在Java中的解决方案:

public class TicketsCost {
    public static void main(String args[]){
        int[] arr  =  {1,5,6,9,28,30};
        System.out.println(findMinCost(arr));
    }
    public static int findMinCost(int[] arr) {
        int[][] dp = new int[arr.length][3];
        int[] tDays = {1,7,30};
        int[] tCost = {2,7,25};

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < 3; j++) {
                if (j==0){
                    dp[i][j]= (i+1)*tCost[j];
                }
                else{
                    int c = arr[i]-tDays[j];
                    int tempCost = tCost[j];
                    int k;
                    if (c>=arr[0] && i>0){
                        for …

问题：一组 n 个硬币放在一排。硬币具有不需要不同的正值。考虑到不能捡起两个相邻的硬币的限制，找出可以收集的最大数量。

它的递归关系是

F(n) = max{cn + F(n ? 2), F(n ? 1)} for n > 1,
F(0) = 0, F(1) = c1.

我的问题是这种递归关系是如何发展的。请有人向我解释这一点。

我正在寻求如何解决这个问题的想法。我的想法是贪婪的方法。

问题是：

你在俄罗斯萨马拉工作了几天，每天都有新的单位工作工资和新的单位食品成本。工作 1 单位消耗 1 单位能量，吃 1 单位食物增加 1 单位能量。以下是您的工作的一些规格：

+你到达时没有钱，但有能量。你的能量永远不会超过你到达时的能量，它永远不会是消极的。

+您每天可以做任何数量的工作（可能根本不做任何工作），仅受您的精力限制。当你的能量为零时，你无法工作。

+您每天可以吃任意数量的食物（可能根本没有任何食物），受您拥有的钱的限制。当你的钱为零时，你不能吃饭。

+您可以在一天结束时进食，进食后无法返回工作。您可以在第二天返回工作。你的真正目标是带着尽可能多的钱回家。计算您可以带回家的最大金额。

例如，考虑 3 天的住宿，其中每天的单位工作报酬如下：收入=[1, 2, 4]。食物的成本是 cost=[1, 3, 6]。你从 e=5 能量单位开始。

*第一天：1 单位工作值 1，1 单位食品成本 1。这一天上班没有经济激励。

*第二天：1 单位工作赚 2，1 单位食品成本 3，因此你花在吃饭上的钱比总收入多，所以这一天没有去上班的经济激励。

*第三天：您每工作单位赚取 4 个单位。今天，食物的成本无关紧要，因为您将直接下班回家。你把所有的精力都花在工作上，收取你的工资：5 x 4 = 20 个单位的钱，然后不买晚饭就回家了。

功能描述 在下面的编辑器中完成功能calculatePro?t。该函数必须返回一个整数，表示在您入住结束时可以带回家的最大收入。

到目前为止我的解决方案（需要改进）：

function calculateProfit(n, earning, cost, e) {
    // Write your code here

    let sum = 0

    let ef = e;

    let count = 0;

    let max = 0;

    for (let i = 0; i < …

这是我最近面临的编程挑战。

您得到的数字小于1000，您需要确定求和到给定数字的素数最少为多少。

例子：

12: 2 (since 12=7+5)
14: 2  (since 14 = 7+7)

Run Code Online (Sandbox Code Playgroud)

如果不可能将给定的数字分解为素数之和，则返回-1。

以下是一些测试用例：

88:2
117:3
374:2
363:3
11:1

Run Code Online (Sandbox Code Playgroud)

两个相邻顶点之间的每个线段的长度为 1 个单位。有多少种方法可以沿着 10 段序列从 A 到 B 而不接触阴影正方形的边或顶点？

我知道答案是 72，但正在努力寻找如何得出该答案。

我试图了解标题提到的codejam 问题的解决方案。具体来说，第三部分为“额外学分”。这是来自 Github 的“kamyu104”的解决方案。

# Copyright (c) 2021 kamyu. All rights reserved.
#
# Google Code Jam 2021 Qualification Round - Problem B. Moons and Embrellas 
# https://codingcompetitions.withgoogle.com/codejam/round/000000000043580a/00000000006d1145
#
# Time:  O(N)
# Space: O(1)
#

def moons_and_umbrellas():
    X, Y, S = raw_input().strip().split()
    X, Y = int(X), int(Y)
    dp = {}
    prev = None
    for c in S:
        new_dp = {}
        for i, j, cost in [('C', 'J', Y), ('J', 'C', X)]:
            if c == j:
                new_dp[i] …

配置

在clojure 1.10.3和openjdk 17.0.1下测试

(def fib
  (memoize #(condp = %
              0 (bigdec 0)
              1 1
              (+ (fib (dec %)) (fib (- % 2))))))

(fib 225) ; line 7

def fib(n):
    dp = [0, 1] + [0] * n
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Syntax error (StackOverflowError) …