动态规划
- 全部主题
按热度排序
从一道DP题出发,浅析DP算法的思路分析与优化方式
DP(Dynamic Programming)是一个让很多人头疼的题目类型,它的题目变化多样,没有所谓的定式,导致很多人在面对DP的时候会显得束手无措,不知道如何下手。
实际上,DP并非无迹可寻,通过总结一些DP题目,我发现,DP其实有着很多的思路可以追寻,而这些思路实际上在不同的题目上是可以共通

632116
关于recursion和DP的一点儿小心得
本人刷题和学数据结构算法已经有一段时间,从最初的Easy题目都啃不动,到现在的medium难度基本没太大问题,中间经历了很多痛苦的挣扎。尤其是很多牵扯到动态规划的题,做的非常难受。其实说白了无非就是一开始没有深刻理解到底什么是递归,什么是动态规划。
简单来说,动态规划就是把每次递归计算出的结果保存

716420
你们都怎么学习递归
我看了有关于递归的视频 总感觉懂了 可是又不是很懂。。

175826
关于动态规划(Dynamic Programming)的一些进阶知识
最近讨论问题时总结的一些内容,写出来分享一下..
1. 三大规划与形式系统
三大规划是指在解决组合优化问题时常用的线性规划(Linear Programming)、整数规划(Integer Programming)以及动态规划 —— 除此以外还有其他的数学规划分支,这里就不提了。而我们最

29135
Google的“+-游戏”最优策略下的O(N^2) DP解法
原题:
给定一个仅由+和-组成的字符串,如“++++-----+++++-----++-+”,两名玩家轮流地将“相邻的两个++flip为--”,直至轮到一方时,如果他不能继续flip,则这名玩家输。问对于给定的字符串,如何判断(在双方都使用最优策略的情况下)先手玩家是否一定能赢?

839424
背包问题全解(背包九讲)
偶然看到了一个非常好的学习背包相关动态规划的资料,基本涵盖了背包问题的所有内容。跟大家分享,希望有帮助,如果觉得有用也求留个米~
作者 崔添翼
背包问题九讲2.0 beta1.2
https://github.com/tianyicui/pack
1 01 背包问题3
1.1 题目

631111
问一道谷歌的面试题 - Rythme pattern
就是这个Rythme pattern的问题 N行诗的Rythme组合
n=1时,只用输出 题目是说因为A =B =C......
n=2时,结果是
n =3时,结果是 (因为AAB和AAC一样 只需要输出AAB。)
我自己用backtracking 找到了 n = 4的结果:
AAAA

315823
【回复就加米】求比较动态规划专题课程
如题,最近看到地主家有推荐educative的 dp的课程,大概40多刀(详见link)https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews
还有就是九章算法

141822
分享一个非常有用的DP解题思路
之前刷lc494的时候看到了discussion里的一个高分回答。
https://leetcode.com/problems/target-sum/discuss/455024/DP-IS-EASY!-5-Steps-to-Think-Through-DP-Questions.
5步快速求解D

4151
有没有什么适合自学dp的教程和网站
本渣只上过data structure没上过算法课 dp啊max overflow啊什么的都没学 但面试不都问这些吗=。=就想说自学一下 看了看cracking interview怎么只讲了fibonacci啊。。。。
想问下地里各位爸爸。。。。有什么网站或教程学dp比较好。。。。。谢谢爸爸们

35049
看到一题 求思路
有一个2d array,要从左上角走到右下角,每次只能往下或者往右,要求求最小的initial hp。hp要始终大于0,等于0或小于0就相当于死了。碰到正值,加hp,碰到负值,减hp。碰到D (double),下一次遇到正值的时候,hp加上那个值的两倍。碰到P (pass),下一次遇到负值的时候,h

99323
问一道狗家onsite的DP题 不太懂
Leetcode上看到的最近newgrad的onsite题目,类似于knapsack,实在想不出来这个DP关系应该怎么写,有没有大神来看看解析一下
Given digits 1-9 with each digit associated with a value. Now we have a w

191613
动态规划模糊点
有没有人跟我一样,总在动态规划最开始int dp = new int或者int dp = new int这里迷糊,看到有的题是m+1,n+1有的却是m,n。到底是什么情况下+1,什么情况不用+1?

165410
G家 面試題
上個月 G家 面試題
一時間只有naive的方法
不知是否有些思路
https://i.imgur.com/ucDApw7.png

115811
打算背诵wildcard matching和regular expression matching
如题,做了一天要挂掉的感觉,看答案的code就觉得确实是这么回事,自己就是想不出来,第二次做背下来了。。。反正code不长,打算像背陋室铭一样背诵下来,刻骨铭心,以前上学那么多课文都通篇背下来了,还差这一两道题吗。。。

5824
求讨论,Google OA题 奇偶跳 该怎么做?
题目如图。
我目前的想法(不一定对):两个dp数组,存储从当前位置分别奇偶跳能否到达最后的位置。然后从后往前遍历数组,同时维护一个递增的list,每次用binary在递增数组里找比当前数字大/小的数。
请问是否正确?是否有更好的方法?

20706
请教一道算法题(答题加米)
一共两种operations,分别是加一、乘4.
求从1到数字N的最小operation次数,并且乘4的操作不能超过X次.谢谢!

89415
求问一道meeting room II的follow up
网上搜到的G家题,题干基本和LC 的meeting room II 一样,但是follow up 是现在只有一间meeting room,然后每个meeting interval 有一个价值,相当于是付给这个meeting room的租金。那么请问,这间meeting room要承担哪些meetin

14105
如何判断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

12575
面试如果被问到DP的题目
敢不敢上来就给最优化的解法?
还是需要按部就班:
第一步: Intuitively, use recursive
第二步: 优化recursive with Top down DP
第三步: 优化Top down with bottom up DP
第四步: More trick

5884