标签: dynamic-programming

我最近遇到了这个问题:"你得到一个布尔表达式,由一串符号'true','false','和','或'和'xor'组成.计算用括号括起来的方法的数量表达式,它将评估为true.例如,有两种方法可以将'true和false xor true'括起来,使其计算结果为true."

我知道这是一个动态编程问题所以我试着自己想出一个解决方案,如下所示.假设我们有一个表达式为ABC .... D,其中'.' 表示任何操作,或者,xor和大写字母表示真或假.让我们说这个大小K表达式产生一个真值的方法的数量是N.当一个新的布尔值E被添加到这个表达式时,有两种方法可以将这个新表达式括起来1.((ABC .... D) .E)即.使用ABC的所有可能的括号....我们在最后添加E. 2.(ABC(DE))即.首先评估DE,然后找到这个大小为K的表达式可以生成的方式的数量.

假设T [K]是具有大小K的表达式产生的方式的数量,则T [k] = val1 + val2 + val3,其中val1,val2,val3计算如下.

1)当E与D分组时

i)它不会改变D的值

ii)它反转D的值

在第一种情况下,val1 = T [K] = N.(因为这减少到初始ABC ... D表达式).在第二种情况下,重新评估dp [K],D值反转,即val1.

2)当E与整个表达式分组时.

// val2包含将使用表达式生成的'true'的数量,这些表达式在ABC的所有带括号的实例中给出'true'...... D i)如果true.E = true则val2 = N

ii)如果为true.E = false则val2 = 0

// val3包含将使用表达式生成的'true'的数量,这些表达式在ABC的所有带括号的实例中给出'false'...... D

iii)如果为假.E =真则则val3 =(2 ^(K-2) - N)= M ie.大小为K的表达式产生错误的方式的数量[2 ^(K-2)是用括号表示大小为K的表达式的方式的数量].

iv)如果为false.E = false则val3 = 0

这是我想到的基本想法,但当我检查其解决方案http://people.csail.mit.edu/bdean/6.046/dp/dp_9.swf时,方法完全不同.有人能告诉我我做错了什么,我怎样才能更好地解决DP问题,以便我能够提出类似上面给出的解决方案.

提前致谢.

Google编程面试中提到了这个问题.我想到了两种相同的方法:

1. 找到所有长度的子序列.这样做的同时计算两个元素的和,并检查它是否等于k.如果是的话,打印是,否则继续搜索.这是一种蛮力的方法.

2. 以非递减顺序对数组进行排序.然后从右端开始遍历数组.假设我们有排序数组{3,5,7,10},我们希望总和为17.我们将从元素10开始,索引= 3,让我们用'j'表示索引.然后包括当前元素并计算required_sum = sum - current_element.之后,我们可以在数组[0-(j-1)]中执行二进制或三进制搜索,以查找是否存在其值等于required_sum的元素.如果我们找到这样一个元素,我们可以打破,因为我们找到了长度为2的子序列,其总和是给定的总和.如果我们没有找到任何这样的元素,那么减小j的索引并重复上述步骤以得到长度=长度为1的子阵列,即在这种情况下通过排除索引3处的元素.

在这里,我们认为数组可能有负整数和正整数.

你能提出比这更好的解决方案吗？DP解决方案可能吗？一种可以进一步降低时间复杂度的解决方案.

我想了解动态规划的概念,通过对MIT OCW课程在这里.关于OCW视频的解释很棒,但我觉得在我将解释实现到代码之前我并不理解它.在实施时,我会参考这里的讲义中的一些注释,特别是注释的第3页.

问题是,我不知道如何将一些数学符号转换为代码.这是我实施的解决方案的一部分(并认为它是正确实现的):

import math

paragraph = "Some long lorem ipsum text."
words = paragraph.split(" ")

# Count total length for all strings in a list of strings.
# This function will be used by the badness function below.
def total_length(str_arr):
    total = 0

    for string in str_arr:
        total = total + len(string)

    total = total + len(str_arr) # spaces
    return total

# Calculate the badness score for a word.
# str_arr is assumed be send …

我的一个朋友刚刚在谷歌接受采访并被拒绝,因为他无法解决这个问题.

我在几天内有自己的面试,似乎无法找到解决问题的方法.

这是问题:

给你一个模式,比如[abab].你也会得到一个字符串,例如"redblueredblue".我需要编写一个程序来告诉字符串是否遵循给定的模式.

几个例子:

模式:[abba]字符串:catdogdogcat返回1

模式:[abab]字符串:redblueredblue返回1

模式:[abba]字符串:redblueredblue返回0

我想到了一些方法,比如获取模式中唯一字符的数量,然后找到字符串的许多唯一子字符串,然后使用hashmap与模式进行比较.然而,如果a的子串是b的一部分,那么结果证明是个问题.

如果你们中的任何人能够帮助我,那真的很棒.:)

更新:

添加信息:模式中可以有任意数量的字符(az).两个字符不代表相同的子字符串.此外,字符不能表示空字符串.

什么是在无向图中找到哈密顿循环的动态规划算法？我在某处看到存在一种具有O(n.2^n)时间复杂度的算法.

任务是从符号+ * ( )(加法,乘法和括号)和数字构建整数1.您将获得一个整数,并且必须使用最少的字符数输出表达式.例如:

4    = 1+1+1+1  
23   = 11+11+1  
242  = (11+11)*11  
1000 = 1+(1+1+1)*(1+1+1)*111 
1997 = (1+1)*(1+1+1)*111+11*11*11 

我们有一个像下面这样的阵列

{1 0 1 0 0 1 0 1}

上面数组中的位数是8

如果我们取范围,[1,5]则范围内的位数[1,5]是[0 1 0 0 1].
如果我们翻转这个范围,那么在翻转后它将是[ 1 0 1 1 0]
翻转[1,5]范围后的总数为1[1 1 0 1 1 0 0 1] = 5

如果我们取范围,[1,6]那么[1,6]范围内的位数是[0 1 0 0 1 0].
如果我们翻转这个范围,那么在翻转之后它将是[ 1 0 1 1 0 1]
翻转[1,5]范围后的总数为1[1 1 0 1 1 0 1 1] = 6

所以答案是范围[1,6],翻转后我们可以获得6个1的数组

有没有一个好的算法可以解决这个问题.我只想到动态编程,因为这个问题可以分解为可以组合的子问题.

我试图回答这个问题,只使用递归(动态编程) http://en.wikipedia.org/wiki/Longest_increasing_subsequence

从文章和SO周围,我意识到最有效的现有解决方案是O(nlgn).我的解决方案是O(N),我找不到它失败的情况.我包括我使用的单元测试用例.

import static org.junit.Assert.assertEquals;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.junit.Test;

public class LongestIncreasingSubseq {

    public static void main(String[] args) {
        int[] arr = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, 1};
        getLongestSubSeq(arr);
    }

    public static List<Integer> getLongestSubSeq(int[] arr) {
        List<Integer> indices = longestRecursive(arr, 0, arr.length-1);
        List<Integer> result = new ArrayList<>();
        for (Integer i : indices) {
            result.add(arr[i]);
        }

        System.out.println(result.toString());
        return result;
    }

    private static List<Integer> longestRecursive(int[] arr, …

获取树的最小顶点覆盖的好算法是什么？

INPUT:

节点的邻居.

OUTPUT:

最小顶点数.

假设给你一个mXn位图,由一个数组M [1..m,1 .. n]表示,其数据全部为0或1.一个全部的块是M [i .. i0形式的子数组,每个位等于1的j .. j0]描述和分析一个有效的算法来找到M中具有最大面积的全一块

我正在尝试制作动态编程解决方案.但是我的递归算法在O(n ^ n)时间内运行,即使在记忆之后我也想不到将它降到O(n ^ 4)以下.有人可以帮我找到更有效的解决方案吗？