以笔记的形式上传我在Leetcode的刷题过程中的总结 | 动态规划篇。
基本要素
转移方程+边界条件
爬楼梯 70
题目分析
转移方程：
边界条件： 元方案要求唯一性
由于只和有关，故使用滚动数组优化空间复杂度
![gif]()
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
int climbStairs(int n) {
int p = 0, q = 0, r = 1;
for (int i = 1; i <= n; i ++) {
p = q;
q = r;
r = p + q;
}
return r;
}
class Solution {
public:
int climbStairs(int n) {
if (n == 1) return 1;
int* dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i ++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
|
使用最小花费爬楼梯
题目分析
cost数组长度len代表了路径中的楼梯数, 则len个阶梯分别对应了数组下标中0到的部分, 本题即求到达下标为n的楼梯所需要的最小花费
与上一道题类似, 这道题也是将爬n个台阶的问题, 转化为了爬个台阶和个台阶的问题, 由此得到该问题的状态转移方程
有点贪心的思想, 每一步都取到最小值的话, 最终结果一定最小
考虑边界条件, 由题设我们知道, 起点可以在下标为0或1的楼梯中选取, 所以到达这两个楼梯的前驱花费一定为0
有了状态转移方程与边界条件, 就可以着手开始解题了
代码实现
利用动态数组节省空间的代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int len = cost.size();
int prev, curr, next;
prev = 0; curr = 0;
for (int i = 0; i <= len; i ++) {
int func1 = prev + cost[i - 1];
int func2 = prev + cost[i - 2];
next = func1 > func2? func1 : func2;
prev = curr;
curr = next;
}
return curr;
}
};
|
删除并获得点数
C++哈希表实现
1
2
3
4
5
| #include <unordered_map>
unordered_map<int, int> hashtable;
hashtable[key] = value;
cout << hashtable[key1] << endl;
|
思路与代码
选取数是任意的，如果每取一个值便要执行删除操作，1是无法进行回溯寻求最优解，2是时间复杂度大，故对vector数组进行排序：
1
| sort(nums.begin(), nums.end());
|
又因为一旦一个值被选取，则与他相同的值均可以被选取，故使用hash表对每个值与其出现的次数进行存储，能优化时间与空间复杂度
接下来考虑状态转移方程，此时问题已经转化为了：在一个有序单调数组中顺序取数，在取了一个数num后，则不能选取num + 1（因为取数操作从无序数组转为有序数组，故而考虑num - 1与考虑num + 1性质相同），而为了获得最大点数，我们必须权衡选取num与选取num + 1两个操作，究竟哪个利润最大
由此得到对于第i个数据对象的状态转移方程
1
2
3
4
| if dp[i] - dp[i - 1] == 1
dp[i] = max(dp[i - 1], dp[i] * N + dp[i - 2])
else
dp[i] = dp[i] * N + dp[i - 2]
|
由于要考虑选和不选的问题，我们使用一个变量last存储当前的dp[i],也就是下一轮循环的前驱了
对于边界条件，我们考虑到value初始值为0的情况，为了避免对首元素的讨论，我们让dp数组的首元素取0即可
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
unordered_map<int, int> m;
sort(nums.begin(), nums.end());
vector<int> dp = {0, nums[0]};
m[nums[0]] = 1;
for (int i = 1; i < nums.size(); i ++) {
m[nums[i]] ++;
if (nums[i] != dp.back())
dp.push_back(nums[i]);
}
int last = dp[1];
dp[1] = dp[1] * m[dp[1]];
for (int i = 2; i < dp.size(); i ++) {
if (dp[i] - last == 1) {
last = d[i];
dp[i] = max(dp[i - 1], dp[i - 2] + dp[i] * m[dp[i]]);
} else {
last = dp[i];
dp[i] = dp[i - 1] + dp[i] * m[dp[i]];
}
}
return dp[dp.size() - 1];
}
};
|
最长有效括号 32
问题分析
求最长括号字串长度, 考虑动态规划
在动态规划问题中, 注重的是由小到大, 由浅入深的问题累积过程. 在本题中, 我们设下标i代表当前括号字符串s的第i个元素, dp[i]表示以当前元素结尾并包含当前元素在内的最长有效括号字串, 下面的讨论以上述条件为依托展开
- 状态转移方程
由于dp[i]表示的是最长有效括号字串, 故要使其值不等于零, 则须满足s[i] ‘)’ , 对s[i - 1]进行讨论:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 1. s[i - 1] == '('
此时s[i - 1]与s[i]构成一对有效括号, dp[i]至少为2
赋值操作: dp[i] = 2
若在此基础上, s[i - 2]存在且dp[i - 2] != 0
说明s[i - 2]是一条有效括号字串的结尾
dp[i] = dp[i] + dp[i - 2]
2. s[i - 1] == ')'
若dp[i - 1] == 0, 说明s[i - 1]为一条有效括号字串的结尾
为了知道s[i]是否为一条有效括号字串的结尾
我们需要考虑下标i - dp[i - 1] - 1的存在性
若其不存在 则s[i]不是有效结尾
若其存在,且s[i - dp[i - 1] - 1] == '('
说明s[i]是有效结尾
dp[i]至少为dp[i - 1] + 2
赋值操作: dp[i] = dp[i - 1] + 2;
若再此基础上, s[i - dp[i - 1] - 2]存在
且dp[i - dp[i - 1] - 2] != 0
说明s[i - dp[i - 1] - 2]是一条有效括号的结尾
dp[i] = dp[i] + dp[i - dp[i - 1] + 2]
|
- 边界条件
我们知道, dp[0] == 0, 因为单个括号不可能有效
在代码实现中, 只需要考虑下标的非负性即可
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public:
int longestValidParentheses(string s) {
int size = s.length();
vector(int) dp(size, 0);
int maxval = 0;
for (int i = 1; i < size; i ++) {
if (s[i] == '(') {
dp[i] = 0;
} else if (s[i] == ')') {
if (s[i - 1] == '(') {
dp[i] = 2;
if (i - 2 >= 0) {
dp[i] += dp[i - 2];
}
} else if (dp[i - 1] > 0 ) {
if (i - dp[i - 1] - 1 >= 0 && dp[i - dp[i - 1] - 1] == '(') {
dp[i] = dp[i - 1] + 2;
if (i - dp[i - 1] - 2 >= 0) {
dp[i] += dp[i - dp[i - 1] + 2];
}
}
}
}
maxval = max(dp[i], maxval);
}
return maxval;
}
}
|
最长回文字串 5
