标签: dynamic-programming

我知道用于解决无限多种面额的硬币变化问题的算法,但是有没有使用DP的有限数量面额算法？

我试图在顶级编码器上解决问题zig zag序列.我的代码的时间复杂度是O(n*n).如何将其减少为O(n)或O(nlog(n))伪代码或算法的解释对我来说真的很有用这是问题陈述.问题陈述

如果连续数字之间的差异在正数和负数之间严格交替,则数字序列称为Z字形序列.第一个差异(如果存在)可以是正面的也可以是负面的.具有少于两个元素的序列通常是Z字形序列.

例如,1,7,4,9,2,5是Z字形序列,因为差异(6,-3,5,-7,3)交替为正和负.相比之下,1,4,7,2,5和1,7,4,5,5不是Z字形序列,第一个是因为它的前两个差异是正的,第二个是因为它的最后差异是零.

给定一系列整数序列,返回序列的最长子序列的长度,该序列是Z字形序列.通过从原始序列中删除一些元素(可能为零)来获得子序列,剩余的元素保持其原始顺序.

这是我的代码

#include <iostream>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;

class ZigZag
{
  public:
  int dp[200][2];
  void print(int n)
  {
      for(int i=0;i<n;i++)
      {
          cout<<dp[i][0]<<endl;
      }
  }
  int longestZigZag(vector<int> a)
  {
      int n=a.size();
      //int dp[n][2];
      for(int i=0;i<n;i++)
      {
          cout<<a[i]<<" "<<"\t";
      }
      cout<<endl;
      memset(dp,sizeof(dp),0);
      dp[0][1]=dp[0][0]=1;
      for(int i=1;i<n;i++)
      {
            dp[i][1]=dp[i][0]=1;

            for(int j=0;j<i;j++)
            {
                if(a[i]<a[j])
                {
                   dp[i][0]=max(dp[j][1]+1,dp[i][0]);
                }
               if(a[j]<a[i])
               {
                    dp[i][1]=max(dp[j][0]+1,dp[i][1]);
               }
            }
            cout<<dp[i][1]<<"\t"<<dp[i][0]<<" "<<i<<endl;
            //print(n);
      }
      cout<<dp[n-1][0]<<endl;
      return max(dp[n-1][0],dp[n-1][1]);
  }
};

Haskell是否提供动态编程的任何工具？在过程语言中,我将使用数组来存储基于递归关系的计算.我如何在Haskell中做类似的事情？

我需要找到涉及重现的算法的复杂性:

T(n) = T(n-1) + ... + T(1) + 1

T(n)是解决大小问题所需的时间n.

master方法在这里不适用,我不能猜测使用替换方法(我不想使用替换方法).我留下了递归树方法.

由于每个节点的子节点数不是常数,我发现很难跟踪每个节点的贡献.底层模式是什么？

我知道我必须在树中找到节点的数量,其中每个节点(k)为其子节点具有从1到1的所有节点k-1.

是否也可以找到T(n)给定公式的确切时间？

好的,这让我发疯了.我解决了一个名为MIXTURES(http://www.spoj.com/problems/MIXTURES/)的spoj问题.我不知道为什么我一直在分段错误.问题中还有一个问题是输入结束没有明确的指标.我想我已经正确处理了,但如果我错了,请纠正我.这是我的代码

#include<stdio.h>
#include<stdlib.h>

typedef struct temp
{
    int modSum;    //the modular sum of the cluster
    int smoke;     //the minimum smoke that a cluster can give.
}clusterInfo;

int fxDP(int *A,int len)     
{
    int i,j,k,smoke1,smoke2;    
    clusterInfo **dpArr=(clusterInfo **)malloc(sizeof(clusterInfo *)*(len-1));

    for(i=0;i<len-1;i++)
        dpArr[i]=(clusterInfo *)malloc(sizeof(clusterInfo)*(len-i-1));   //len- ( (i+2) -1)= len-i-1
    //dpArr[i] gives info of all clusters of length i+2

    //base case    for clusterLength=2
    for(i=0;i<len-1;i++)
    {           
        dpArr[0][i].modSum=(A[i]+A[i+1])%100;
        dpArr[0][i].smoke=A[i]*A[i+1];
    }
    //endBase Case

    //induction
    for(i=1;i<len-1;i++)   //lengthOfCluster=i+2
    {   
        for(j=0;j<len-i-1;j++)    //len-i-1+i+2-1=len
        {   
            smoke1=(dpArr[i-1][j].modSum*A[j+(i+2)-1]) + …

我花了很多时间来学习使用迭代实现/可视化动态编程问题,但我发现它很难理解,我可以使用memoization的递归实现相同的但是与迭代相比它很慢.

有人可以通过硬问题的例子或使用一些基本概念来解释相同的问题.像矩阵链乘法,最长的回文子序列和其他.我可以理解递归过程,然后记住重叠的子问题以提高效率,但我无法理解如何使用迭代来做同样的事情.

谢谢!

如果我们愿意的话,我的一位教授给了我们一个在假日期间考虑的问题,而且我不确定解决问题的正确方法.

问题如下:我们有N条线(1≤N≤10^ 6)从A点到B点,但不知道哪条线末端对应于哪条线开始.有三种方法可以解决这个问题:

• 在A点和B点之间旅行
• 连接电线.(这意味着你接受一部分电线并连接它们,这样你就可以将它们的结尾用作一个单一的结尾)
• 测试电线是否连接.(您可以将其想象为电源线:例如,如果某些电线在A点连接,并且您在B点为这些连接电缆中的一条供电,则可以看到哪些电缆已连接,因为它们也将通电)

目标是计算A和B之间所需的最小旅行次数.

例如,对于3根电线,我们需要2次行程:我们连接两根电线并调用第三根电线A.然后我们前往另一点并测试哪根电线未连接到任何其他两根电线.这必须是电线A.然后我们将A与另一根电线连接,称之为B并返回.现在我们必须找到连接到A的电缆,这必须是B,第三个必须是C.

不幸的是,对于某些N来说,不可能弄清楚哪条线是哪条,例如N = 2.(我很确定N = 2是唯一的一条).N = 1表示零旅行.

任何关于如何处理这个问题的建议都非常感谢.

已经有2个月了,我一直在深入研究JavaScript以及它的库和框架.我听到我高中的其他学生告诉我汇编将取代JavaScript.这是真的？

还有一个问题,你推荐哪种语言用于接近JavaScript的后端开发？我真的不希望任何人成为一个破碎的艺术家.我听到很多JavaScript开发人员已经解决并被替换,因为它只是一种讨厌的语言.

在动态编程问题中,有一个包含先前案例的地图是很正常的,每次到达新状态时,都必须检查它是否已经在地图中,如果是,则使用它,如果不是,则添加它.我想知道这两种方式之间在性能和风格方面有什么好处:

Value value;
if(!map.contains(key)){
    value = calculateValue();
    map.put(key, value);
} else {
    value = map.get(key);
}

还有这个:

if(!map.contains(key)){
    map.put(key, calculateValue());
}
Value value = map.get(key);

第二个似乎效率较低,但允许我避免使用可能导致错误的未初始化变量.

问题:您将获得不同面额的金币和总金额.编写一个函数来计算构成该数量所需的最少数量的硬币.如果这笔钱不能由任何硬币组合弥补,则返回-1.

例1:

输入:coins = [1,2,5],金额= 11输出:3说明:11 = 5 + 5 + 1

例2:

输入:coins = 2,金额= 3输出:-1

You may assume that you have an infinite number of each kind of coin.

我的代码:

public int coinChange(int[] coins, int amount) {
    Arrays.sort(coins);
    int new_amount=amount;
    int count_coin=0;
    int q=0,r=0,a=0;
    int k=coins.length-1;


    while(amount>0 && k>=0) {

            q = new_amount / coins[k];
            count_coin = count_coin + q;
            r = new_amount % coins[k];
            new_amount=r;
            a+=q*coins[k];
            k--;



    }


    if(a==amount){
        return count_coin;
    }
    else{
        return -1;
    } …