登录
动态规划
    • 全部主题
    按热度排序
    从一道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