一、labuladong动态规划模板思路
wiki:https://labuladong.gitee.io/algo/di-ling-zh-bfe1b/dong-tai-g-1e688/
题目:
动态规划模板思路:
二、我自己如何理解【状态】【选择】
以714题目《最佳时机去买卖股票+手续费》为例子:
1.确定 【状态】 -- 寻找原问题和子问题中,变化的“结果”变量(而不是一个选择/动作)
原问题:第N天,股票账户的最大利润
子问题:第N-1天,股票账户的最大利润
其中,变化的变量有【天数】,以及从子问题到原问题的【是否持有股票状态】的变化
请注意:为何状态是【是否持有股票状态】,而不是【买】【卖】【休息】?
因为买、卖、休息,都是动作(可以理解为二叉树的树枝,是变化的路径)。
动作做完后的静态状态【是否持有股票状态】,才是变化后的结果(可以理解为二叉树的节点,是变化的结果)
2.确定【选择】-- 就是每一个子问题能操作的动作(有哪些导致状态变化的行为)
显而易见,就是三个动作:
- 买
- 卖
- 休息(不操作)
3.明确dp数组的定义 -- 每个状态都需要呈现一个维度,若有两个状态就需要二维数组
本题中,需要的是:
最后一【天】的【未持有股票状态(因为不操作肯定买要利润大)】的 {最大利润}
- 【】中的就是状态
- {} 中的是dp数组内的值,也是该问题需要的解
标签:总结,状态,动作,必看,--,股票,问题,变化,Leetcode From: https://www.cnblogs.com/frankcui/p/17547956.html