登录
动态规划
    • 全部主题
    按热度排序
    从一道DP题出发,浅析DP算法的思路分析与优化方式
    DP(Dynamic Programming)是一个让很多人头疼的题目类型,它的题目变化多样,没有所谓的定式,导致很多人在面对DP的时候会显得束手无措,不知道如何下手。 实际上,DP并非无迹可寻,通过总结一些DP题目,我发现,DP其实有着很多的思路可以追寻,而这些思路实际上在不同的题目上是可以共通
    chinsnlia
    6321
    16
    关于recursion和DP的一点儿小心得
    本人刷题和学数据结构算法已经有一段时间,从最初的Easy题目都啃不动,到现在的medium难度基本没太大问题,中间经历了很多痛苦的挣扎。尤其是很多牵扯到动态规划的题,做的非常难受。其实说白了无非就是一开始没有深刻理解到底什么是递归,什么是动态规划。 简单来说,动态规划就是把每次递归计算出的结果保存
    钢铁侠吉米
    7164
    20
    你们都怎么学习递归
    我看了有关于递归的视频 总感觉懂了 可是又不是很懂。。
    Colley
    1758
    26
    关于动态规划(Dynamic Programming)的一些进阶知识
    最近讨论问题时总结的一些内容,写出来分享一下.. 1. 三大规划与形式系统 三大规划是指在解决组合优化问题时常用的线性规划(Linear Programming)、整数规划(Integer Programming)以及动态规划 —— 除此以外还有其他的数学规划分支,这里就不提了。而我们最
    magicsets
    2913
    5
    Google的“+-游戏”最优策略下的O(N^2) DP解法
    原题: 给定一个仅由+和-组成的字符串,如“++++-----+++++-----++-+”,两名玩家轮流地将“相邻的两个++flip为--”,直至轮到一方时,如果他不能继续flip,则这名玩家输。问对于给定的字符串,如何判断(在双方都使用最优策略的情况下)先手玩家是否一定能赢?
    stellari
    8394
    24
    背包问题全解(背包九讲)
    偶然看到了一个非常好的学习背包相关动态规划的资料,基本涵盖了背包问题的所有内容。跟大家分享,希望有帮助,如果觉得有用也求留个米~ 作者 崔添翼 背包问题九讲2.0 beta1.2 https://github.com/tianyicui/pack 1 01 背包问题3 1.1 题目
    Luckyu2015
    6311
    11
    问一道谷歌的面试题 - Rythme pattern
    就是这个Rythme pattern的问题 N行诗的Rythme组合 n=1时,只用输出 题目是说因为A =B =C...... n=2时,结果是 n =3时,结果是 (因为AAB和AAC一样 只需要输出AAB。) 我自己用backtracking 找到了 n = 4的结果: AAAA
    杨超越
    3158
    23
    【回复就加米】求比较动态规划专题课程
    如题,最近看到地主家有推荐educative的 dp的课程,大概40多刀(详见link)https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews 还有就是九章算法
    venturekwok
    1418
    22
    分享一个非常有用的DP解题思路
    之前刷lc494的时候看到了discussion里的一个高分回答。 https://leetcode.com/problems/target-sum/discuss/455024/DP-IS-EASY!-5-Steps-to-Think-Through-DP-Questions. 5步快速求解D
    xiaodingjiayou
    415
    1
    有没有什么适合自学dp的教程和网站
    本渣只上过data structure没上过算法课 dp啊max overflow啊什么的都没学 但面试不都问这些吗=。=就想说自学一下 看了看cracking interview怎么只讲了fibonacci啊。。。。 想问下地里各位爸爸。。。。有什么网站或教程学dp比较好。。。。。谢谢爸爸们
    mdzzxswl
    3504
    9
    看到一题 求思路
    有一个2d array,要从左上角走到右下角,每次只能往下或者往右,要求求最小的initial hp。hp要始终大于0,等于0或小于0就相当于死了。碰到正值,加hp,碰到负值,减hp。碰到D (double),下一次遇到正值的时候,hp加上那个值的两倍。碰到P (pass),下一次遇到负值的时候,h
    glambertjay
    993
    23
    问一道狗家onsite的DP题 不太懂
    Leetcode上看到的最近newgrad的onsite题目,类似于knapsack,实在想不出来这个DP关系应该怎么写,有没有大神来看看解析一下 Given digits 1-9 with each digit associated with a value. Now we have a w
    miawallace
    1916
    13
    动态规划模糊点
    有没有人跟我一样,总在动态规划最开始int dp = new int或者int dp = new int这里迷糊,看到有的题是m+1,n+1有的却是m,n。到底是什么情况下+1,什么情况不用+1?
    cindyyang
    1654
    10
    G家 面試題
    上個月 G家 面試題 一時間只有naive的方法 不知是否有些思路 https://i.imgur.com/ucDApw7.png
    lzm34589
    1158
    11
    打算背诵wildcard matching和regular expression matching
    如题,做了一天要挂掉的感觉,看答案的code就觉得确实是这么回事,自己就是想不出来,第二次做背下来了。。。反正code不长,打算像背陋室铭一样背诵下来,刻骨铭心,以前上学那么多课文都通篇背下来了,还差这一两道题吗。。。
    牧moon
    582
    4
    求讨论,Google OA题 奇偶跳 该怎么做?
    题目如图。 我目前的想法(不一定对):两个dp数组,存储从当前位置分别奇偶跳能否到达最后的位置。然后从后往前遍历数组,同时维护一个递增的list,每次用binary在递增数组里找比当前数字大/小的数。 请问是否正确?是否有更好的方法?
    东尼老师
    2070
    6
    请教一道算法题(答题加米)
    一共两种operations,分别是加一、乘4. 求从1到数字N的最小operation次数,并且乘4的操作不能超过X次.谢谢!
    小水
    894
    15
    求问一道meeting room II的follow up
    网上搜到的G家题,题干基本和LC 的meeting room II 一样,但是follow up 是现在只有一间meeting room,然后每个meeting interval 有一个价值,相当于是付给这个meeting room的租金。那么请问,这间meeting room要承担哪些meetin
    一亩三分地匿名用户
    1410
    5
    如何判断dp array size应该是len 还是 len +1
    我在做动态规划的时候,不是很清楚什么时候dp的size应该是A.length 还是A.length+1.比如是说下面的Jump Game,好像就用 boolean dp = new boolean。 * * @param A: A list of integers * @retur
    pxu
    1257
    5
    面试如果被问到DP的题目
    敢不敢上来就给最优化的解法? 还是需要按部就班: 第一步: Intuitively, use recursive 第二步: 优化recursive with Top down DP 第三步: 优化Top down with bottom up DP 第四步: More trick
    myonlysunshine
    588
    4