登录
动态规划
    • 全部主题
    按时间排序
    分享一个非常有用的DP解题思路
    之前刷lc494的时候看到了discussion里的一个高分回答。 https://leetcode.com/problems/target-sum/discuss/455024/DP-IS-EASY!-5-Steps-to-Think-Through-DP-Questions. 5步快速求解D
    xiaodingjiayou
    994
    1
    一道题求解惑
    leetcode 416 我用两种解法都能ac,能写出两种解法完全不是因为融会贯通和举一反三,而是因为看其他的01背包问题的解题方法,这两种都出现过,但其实自己并不能理解为什么两种方法都行。 说实话解法一我倒能理解一点,因为可以根据一个没有mem优化的解法推演出来,解法二就完全弄不明白了
    JoyForce
    724
    7
    [求解答]二维矩阵dp题
    求教大佬们一道题。2D矩阵要从左上到达右下,每次步长等于所在位置的值,可以向右或向下走,求最少步数。因为有时间限制,所以应该是得用dp做,想问下具体思路和实现。在此提前感谢!
    匿名
    556
    4
    打算背诵wildcard matching和regular expression matching
    如题,做了一天要挂掉的感觉,看答案的code就觉得确实是这么回事,自己就是想不出来,第二次做背下来了。。。反正code不长,打算像背陋室铭一样背诵下来,刻骨铭心,以前上学那么多课文都通篇背下来了,还差这一两道题吗。。。
    牧moon
    987
    4
    你们都怎么学习递归
    我看了有关于递归的视频 总感觉懂了 可是又不是很懂。。
    Colley
    3064
    26
    面试如果被问到DP的题目
    敢不敢上来就给最优化的解法? 还是需要按部就班: 第一步: Intuitively, use recursive 第二步: 优化recursive with Top down DP 第三步: 优化Top down with bottom up DP 第四步: More trick
    myonlysunshine
    1437
    4
    求解Pramp上一道类似edit distance的DP题
    在Pramp上做了一道和edit distance类似的题。后面我写了我的javascript代码,但是有些edge case就是过不去。 有没有哪个大神可以指点一下这个题怎么做的 Pramp 链接: https://www.pramp.com/challenge/5j2xWAx1qPtlZ
    miawallace
    1004
    3
    大家见过这道LIS变种题吗
    给定一个array,要求reverse 一个 subarray,使得LIS最长 请问用动归怎么做
    innerpeace318
    360
    0
    关于LC638的运行效率问题
    本人小菜一枚,关于LC638请教各位大佬。这里是题目的链接 https://leetcode.com/problems/shopping-offers/submissions/ 我用了recursion+memoization的方法通过了,但是运行时间上比较惨(如下图)。 我实在
    BobbyBear
    315
    2
    第一次解DP题,想问下这个算DP吗?
    Leetcode 198. House Robber 我理解的动态规划就是递归+把重复的值存起来下次直接用。所以我在解这道题的时候先写了递归算法(当然最后超时通不过),然后再加了一个list来存算过的值。 那这个解法算动态规划吗?还是只是递归的一种好一点的解法? class Solut
    tianxindew
    895
    10
    word search变形 oa题
    这个题当然可以纯dfs 但好像用dp理论上应该是有帮助的 但key比较复杂 x y 和word index trie可能也有用 但还没想明白怎么用 因为不可能上来建trie
    Smilenceyu
    967
    1
    看到一题 求思路
    有一个2d array,要从左上角走到右下角,每次只能往下或者往右,要求求最小的initial hp。hp要始终大于0,等于0或小于0就相当于死了。碰到正值,加hp,碰到负值,减hp。碰到D (double),下一次遇到正值的时候,hp加上那个值的两倍。碰到P (pass),下一次遇到负值的时候,h
    glambertjay
    1361
    23
    求教一道dp
    BiuBiuBiu 每次出去玩都要去坐地铁,BiuBiuBiu 观察到,当地铁上人比较少的时候,大家都会选择那些与其他人不相邻的座位,现在地铁上有 n 个座位排成一排,1 号座位与 2 号相邻,n 号座位与 n-1 号相邻,除了 1 号与 n 号座位,任意 i 号座位都与 i-1 和 i+1 号座位
    咫尺天涯2121
    1235
    4
    用动态规划怎么做这道《The Cheapest Flight》
    谁可以讲讲,动DP怎么做这道题吗? "We need to fly home as cheaply as possible so that more money is left for gifts. Aunt Lidia asked for different kinds of cheeses
    李浩泉
    1375
    5
    【刷题笔记】Leetcode #1143. Longest Common Subsequence
    【题目】Given two strings text1 and text2, return the length of their longest common subsequence. 【思路1:brute force】 穷举text 1 的所有subsequence,检查是否存在于tex
    liuzz10
    830
    2
    【回复就加米】求比较动态规划专题课程
    如题,最近看到地主家有推荐educative的 dp的课程,大概40多刀(详见link)https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews 还有就是九章算法
    venturekwok
    2200
    22
    Leetcode 689 Maximum Sum of 3 Non-Overlapping Subarrays
    想写一个Dp 的算法, 试了很多遍,都不能保证全过。求指点。想法就是用4个数组,第一个都是0,第二个是1个subarray 的 sum, 但是只记录到此为止的最大值,如果到此为止的sum是10,但是前面有subarray的sum是20,那么就记录20, 第三个数组记录2 个subarray 的 su
    ThinkDeeper2
    1129
    1
    面试的时候DP问题先递归bruteforce再用top down加mem优化有毛病吗
    我觉得相对于bottom up来说 这种解答对于我来说最intuitive 但是因为要maintain call stack 不知道面试的时候使用此法会不会被嫌弃 有人可以share一下经验或者心得吗
    biorainy
    976
    2
    矩形密铺问题求解
    面试的时候被问到在一个mxn的矩形想要铺axb的矩形,问最多铺多少个?没有思路,想到可能是dp,可是不知道如何dp。 如果是dp的话写出来转移方程就行,贪心解法也可以。 和朋友讨论了好久没有结果,求地里大神给点思路
    烤冷面
    737
    3
    关于edit distance
    学了两天dp遇到了一点瓶颈,我看lev distance那个递归公式,觉得它是不是在说每一次delete操作只能处理字符串a最后一位的字符呢,然后变成一个关于无最后一位的子字符串的最优问题, 但是问题定义的delete操作应该是每一次都可以delete任意一个地方的char吧 但那样的话就有太多的可
    Loceyi
    522
    2