我是靠谱客的博主 眯眯眼鼠标,这篇文章主要介绍leetcode dp 动态规划专题-1动态规划实例,(代码并不一定是时间/空间最优化的,但是一定完整体现了DP思想),现在分享给大家,希望可以做个参考。
动态规划
动态规划明显的优点:可以解决暴力超时的题目
动态规划可以认为是可以递推的数组,满足以下要素
- 初始值, 如a0, a1(通常由最简单情况可以得到)
- 当前值可以由历史值推断而来:an=an-1+an-2或者
a n = ∑ i = 1 n − 1 a i , a_{n}=sumlimits_{i=1}^{n-1}a_{i}, an=i=1∑n−1ai,(这一点最难推断得出) - 每个值都有某种含义,表示一个特定情况下的状态,最后的解可以由an或者多个ai得出(这一点若选取不当则第2点无法得出)
实际运用时,往往先考虑第3点,根据设定的值含义推断出第2点的递推公式,然后得到第1点:取恰当的初始值。
实例,(代码并不一定是时间/空间最优化的,但是一定完整体现了DP思想)
一、70. 爬楼梯
三要素:
- 考虑以下的状态:对于某种阶梯数n,对应一种状态:爬到楼顶的方法数,那么可以设置dp[i]:阶梯数为i时爬到楼顶的方法,1<=i<=n
- 递推公式则为:dp[i]=dp[i-1]+dp[i-2],3<=i<=n
- 从递推公式中可以取初始值为:dp[1]=1,dp[2]=2
- 结果就是:dp[最后一天]
代码
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13class Solution { public: int climbStairs(int n) { if (n <= 2) return n; //特殊情况 vector<int> dp(n+1,0); dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; ++i) dp[i] = dp[i-1] + dp[i-2]; return dp[n]; } };
二、121. 买卖股票的最佳时机
注意一个陷阱:并不一定非要完成一笔买入+卖出交易
三要素:假设输入数组为prices
- 考虑以下的状态:对于某一天i(这里i可以取0,0<=i<=输入数组.size()-1),对应三种状态:到这天为止,未操作股票/已买入/已买入卖出,那么可以设置dp[i][0]:第i天未操作股票;dp[i][1]:第i天已买入股票;dp[i][2]:第i天已买入卖出股票,1<=i<=n
- 递推公式则为:
不操作股票dp[i][0] = dp[i-1][0];
当天买入与之前买入的比较dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]);
当天卖出与之前卖出的比较dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i]); - 初始值可以取:第零天:dp[0][0]=dp[0][2]=0,dp[0][1]=-1*prices[0],这里的第零天相当于实际意义上的第一天
- 结果就是:max(dp[某一天][0], dp[某一天][2])
代码
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution { public: int maxProfit(vector<int>& prices) { if (prices.empty()) return 0; vector<vector<int>> dp(prices.size(), vector<int>(3, 0)); dp[0][1] = -1*prices[0]; for (int i = 1; i < prices.size(); ++i) { dp[i][0] = dp[i-1][0]; dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]); dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i]); } return max(dp[prices.size()-1][0], dp[prices.size()-1][2]); } };
三、198. 打家劫舍
三要素:假设输入数组为nums
- 考虑以下的状态:dp[i]:仅仅有前i间屋子,偷窃到的最高金额
- 递推公式则为:偷这间加上隔一间之前的金额或者保持已有最大金额dp[i] = max(dp[i-2]+nums[i], dp[i-1])
- 初始值可以取:dp[0]=nums[0], dp[1]=max(nums[1],nums[0])
- 结果就是:dp[某一天]
代码
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution { public: int rob(vector<int>& nums) { if(nums.size()==0) return 0; else if(nums.size()==1) return nums[0]; else if(nums.size()==2) return max(nums[0],nums[1]); else { int l = nums.size(); vector<int> dp(l); dp[0] = nums[0]; dp[1] = max(nums[0],nums[1]); for (int i = 2; i < l; ++i) dp[i] = max(dp[i-2]+nums[i], dp[i-1]); return dp[l-1]; } } };
四、303. 区域和检索 - 数组不可变
三要素:假设输入数组为nums
- 考虑以下的状态:dp[i]:nums[0]至nums[i-1]的和,dp[0]是0,dp[0]的设置目的见第4点
- 递推公式则为:dp[i] = dp[i-1]+nums[i]
- 初始值可以取:没有初始值
- 结果就是:索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点:为两段和之差:dp[j+1]-dp[i],此处dp[0]的存在意义:没有任何元素
代码
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class NumArray { private: vector<int> vnums; public: NumArray(vector<int>& nums) { vnums.reserve(nums.size() + 1); vnums[0] = 0; for (int i = 1; i <= nums.size(); ++i) vnums[i] = vnums[i - 1] + nums[i - 1]; } int sumRange(int i, int j) { return vnums[j + 1] - vnums[i]; } };
五、746. 使用最小花费爬楼梯
三要素:假设输入数组为cost
- 考虑以下的状态:dp[i]:走到第i阶梯的最小花费
- 递推公式则为:dp[i] = min(dp[i-2], dp[i-1]) + cost[i]
- 初始值可以取:dp[0] = cost[0], dp[1] = cost[1]
- 结果就是:min(dp[cost.size()-1], dp[cost.size()-2])
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution { public: int minCostClimbingStairs(vector<int>& cost) { int l = cost.size(); vector<int> dp(l); dp[0] = cost[0]; dp[1] = cost[1]; for (int i = 2; i < l; ++i) dp[i] = min(dp[i-1],dp[i-2]) + cost[i]; return min(dp[l-1], dp[l-2]); } };
六、1025. 除数博弈
三要素:假设输入值为N
- 考虑以下的状态:dp[i]:数字是i时爱丽丝能否获胜
- 递推公式则为:如果存在j<i, i%j==0, 且dp[i-j]==false则dp[i] = true, 否则dp[i]=false
- 初始值可以取:dp[1] = false, 不存在dp[0] (这个是用来方便下标处理的)
- 结果就是:dp[N]
代码
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution { public: bool divisorGame(int N) { vector<bool> dp(N+1,false); for (int i = 2; i <= N; ++i) { for (int j = 1; j <= i/2; ++j) { if (i%j == 0 && !dp[i-j]) { dp[i] = true; break; } } } return dp[N]; } };
最后
以上就是眯眯眼鼠标最近收集整理的关于leetcode dp 动态规划专题-1动态规划实例,(代码并不一定是时间/空间最优化的,但是一定完整体现了DP思想)的全部内容,更多相关leetcode内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复