算法（八）动态规划
动态规划
- 分析问题，制定dp方程式；
- 初始化dp
- for求解dp
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
dp[i] = dp[i-1] + dp[i-2]
杨辉三角
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
dp[i] = max(dp[i-1], dp[i-2]+nums[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int rob(vector<int>& nums) {
// 动态规划问题要判断nums大小为1和2时；
if (nums.size() == 1)
return nums[0];
vector<int> ans(nums.size(), 0);
ans[0] = nums[0];
ans[1] = std::max(nums[0], nums[1]); // 注意dp[1]的初始化：第二家最大金额只能是两家中的一家。
if (nums.size() == 2)
return std::max(nums[0], nums[1]);
for (int i = 2; i < nums.size(); i++) {
ans[i] = std::max(ans[i - 1], ans[i - 2] + nums[i]);
}
return ans.back();
}
完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
--动态规划/image.png)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1);
for(int i = 1; i <= n; i++) {
int cur = INT_MAX;
for(int j = 1; j * j <= i; j++) {
cur = std::min(cur, dp[i-j*j]);
}
dp[i] = cur + 1;
}
return dp[n];
}
};
零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
--动态规划/image-1.png)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int coinChange(vector<int>& coins, int amount) {
int Max = amount + 1;
vector<int> dp(amount+1, Max);
dp[0] = 0;
for(int i = 1; i <= amount; i++) {
for(int j = 0; j < coins.size(); j++) {
if(i - coins[j] >= 0) {
dp[i] = std::min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
--动态规划/image-2.png)
最长递增序列
--动态规划/image-3.png)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lengthOfLIS(vector<int>& nums) {
if(nums.size() == 0) return 0;
int n = nums.size();
vector<int> dp(n+1,1);
for(int i = 1; i < n+1; i++) {
for(int j = 1; j < i; j++) {
// 逻辑pos和实际pos
if(nums[j-1] < nums[i-1]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
最大子乘积
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组 （该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
--动态规划/image-5.png)
购买股票
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
1
2
3
4
5
6
7
8
int maxProfit(vector<int>& prices) {
int cost = prices[0], price = 0;
for(int i = 1; i < prices.size(); i++) {
price = max(price, prices[i] - cost);
cost = min(prices[i], cost);
}
return price;
}
购买股票2
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。返回 你能获得的最大利润 。
当股票价格下跌时，一直更新count，上升时不更新，下跌时计算利润。注意边缘情况，如果最后一天是上升的，需要在最后一天计算利润。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxProfit(vector<int>& prices) {
int ans = 0, count = 0;
for(int cur = 0; cur < prices.size(); cur++) {
if((cur != 0 && prices[cur-1] > prices[cur])) {
ans += prices[cur-1] - prices[count];
count = cur;
}
else {
if(cur == prices.size() - 1) {
ans += prices[cur] - prices[count];
}
}
}
return ans;
}
贪心
递增的三元子序列
给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。贪心，维护两个变量，最小值和次小值。这两个变量的更新是这样的。 遍历整个数组，如果当前元素小于最小值，更新最小值；大于最小值但小于次小值，更新次小值；大于次小值，返回true。
1
2
3
4
5
6
7
8
9
10
11
12
13
bool increasingTriplet(vector<int>& nums) {
int min = INT_MAX, secondMin = INT_MAX;
for(int i = 0; i < nums.size(); i++) {
if(nums[i] <= min) {
min = nums[i];
} else if(nums[i] <= secondMin) {
secondMin = nums[i];
} else {
return true;
}
}
return false;
}
跳跃游戏
反序遍历数组，维护一个变量，记录当前位置能否到达最后一个位置。如果当前位置能到达最后一个位置，更新最后一个位置为当前位置。
1
2
3
4
5
6
7
8
9
bool canJump(vector<int>& nums) {
int last = nums.size() - 1;
for(int i = nums.size() - 1; i >= 0; i--) {
if(i + nums[i] >= last) {
last = i;
}
}
return last == 0;
}
跳跃游戏2
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处，返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
思路同样是反向查找出发位置。对于某个位置，如果有多个位置能够到达它，贪心的选择最远的位置，也就是下标最小的位置。这样一直找到起始位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int jump(vector<int>& nums) {
int last = nums.size() - 1;
int count = 0;
while(last != 0) {
for(int i = 0; i < last; i++) {
if(i + nums[i] >= last) {
last = i;
count++;
break;
}
}
}
return count;
}
加油站
核心思想：遍历一遍数组，当当前加油站已经无法支持你继续开下去之后，那么开始的加油站到当前加油站之间的加油站都不能支持你开过当前加油站，需要从当前加油站的下一个加油站开始了。
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 canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
int i = 0;
while(i < n) {
int sumOfGas = 0, sumOfCost = 0;
int cnt = 0;
while(cnt < n) {
int j = (i + cnt) % n;
sumOfGas += gas[j];
sumOfCost += cost[j];
if(sumOfCost > sumOfGas) break;
cnt++;
}
if(cnt == n) {
// 开了一圈了
return i;
}
else {
// 从无法抵达的加油站的下一个加油站出发 贪心点
i = i + cnt + 1;
}
}
return -1;
}