我是靠谱客的博主 眯眯眼鼠标，这篇文章主要介绍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内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![[LeetCode]Regular Expression Matching、Wildcard Matching](/uploads/reation/bcimg1.png)
![【从零开始的动态规划02】——双串问题dp[i][j]，矩阵DP，无串线性DP](/uploads/reation/bcimg7.png)
发表评论 取消回复