wowowo123

题解

动态规划(1) 未归档(4)

/ 注册

全部文章 / 题解（共93篇）

leetcode 77 组合

通过回溯加判断条件剪枝，如果加入路径的值不能比前一个值小。组合问题通常需要通过某种顺序展开组合问题，相对于排列问题而言，不计较一个组合内元素的顺序性（即 [1, 2, 3] 与 [1, 3, 2] 认为是同一个组合），因此很多时候需要按某种顺序展开搜索，这样才能做到不重不漏。作者：liwei...

2021-04-04

0 559

leetcode 47 全排列2

使用递归，剪枝 class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: result=[] def dfs(i,path,visit,result): ...

2021-04-04

0 459

leetcode 113 路径总和2

通过回溯深搜，因为题目要求的是路径，所以当节点的值满足目标值以及没有左右子节点（为叶子节点）返回，每次将当前遍历的节点放入path数组，同时目标进行作差。同样需要注意path数组的浅复制path[:],否则result中的结果为空，因为会随着递归后path数组为空而变化。 python数组可以使...

2021-04-03

0 459

leetcode 46 全排列

通过回溯算法，在纸上画出求解问题的树形图，想清递归结构考虑如何剪枝。做题的时候，建议先画树形图，画图能帮助我们想清楚递归结构，想清楚如何剪枝。拿题目中的示例，想一想人是怎么做的，一般这样下来，这棵递归树都不难画出。在画图的过程中思考清楚：分支如何产生；题目需要的解在哪里？是在叶子结点、还...

2021-04-03

0 513

leetcode 120 三角形最小路径和

把三角形看成一个上三角或者下三角(等腰三角形)，然后设置状态转移公式，当没到每行的最后一个的时候，以及每行的第一个，都可以有两种方法到达当前位置，选择最小的路径和。 class Solution: def minimumTotal(self, triangle: List[List[int...

2021-04-03

0 502

leetcode213 打家劫舍2

问题将数组改为循环数组，也就是头和尾不能一起偷盗，所以就进行两次计算，一次将数组去除头元素，一次将数组去掉尾元素。 class Solution: def rob(self, nums: List[int]) -> int: if len(nums)==0: ...

2021-04-03

0 637

leetcode 198 打家劫舍

使用动态规划，看第几间屋子是偷还是不偷，偷的话由之前的没偷的状态转移过来，不偷的话之前可能偷了也可能没偷。 class Solution: def rob(self, nums: List[int]) -> int: dp=[[0,0] for _ in range(...

2021-04-03

0 455

leetcode 64 最小路径和

动态规划的想法，dp数组中存储的位置代表每一条路径到达当前位置的最小路径和，每一个状态进行转移的时候只和左面和上面的位置有关。 class Solution: def minPathSum(self, grid: List[List[int]]) -> int: dp...

2021-04-03

0 465

leetcode 714 股票手续费问题来自专栏

使用动态规划方法，dp数组的状态和之前多次买卖的状态数量一样，一种是天数，一种是持有还是不持有，当股票卖出（买入也可以）需要减去手续费用，注意这个手续费用只能计算一次。 class Solution: def maxProfit(self, prices: List[int], fee: ...

2021-04-02

0 512

leetcode 309 股票买卖冷冻期来自专栏

状态主要分为两种，一种是天数，一种是是否持股以及是否处在冷冻期，这两种状态是复合的，要么持有，要么不持有不冷冻，要么不持有在冷冻。所以设置dp数组，状态转移如下 dp[i][0]=max(dp[i-1][0],dp[i-1][2]-prices[i]) d...

2021-04-02

0 506