第八课动态规划
2021-11-20
6分钟阅读时长
70. 爬楼梯
class Solution {
public:
int climbStairs(int n) {
std::vector<int> dp(n + 3, 0);
dp[1] = 1;
dp[2] = 1;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
198. 打家劫舍
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0) {
return 0;
}
if (nums.size() == 1) {
return nums[0];
}
//设第一个房间的最优解dp[i]
std::vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
dp[1] = std::max(nums[0], nums[1]);
for (int i = 2; i < nums.size(); i++) {
dp[i] = std::max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.size() - 1];
}
};
53. 最大子序和
class Solution {
public:
int maxSubArray(vector<int>& nums) {
std::vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
int res_max = dp[0];
for (int i = 1; i < nums.size(); i++) {
//递推公式
dp[i] = std::max(dp[i - 1] + nums[i], nums[i]);
if (res_max < dp[i]) {
res_max = dp[i];
}
}
return res_max;
}
};
322. 零钱兑换
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
std::vector<int> dp;
//初始化dp数组
for (int i = 0; i <= amount; i++) {
dp.push_back(-1);
}
dp[0] = 0;//金额0最优解0
for (int i = 1; i <= amount; i++) {
//循环各个面值，找到dp[i]最优解
for (int j = 0; j < coins.size(); j++) {
if (coins[j] <= i && dp[i - coins[j]] != -1) {
if (dp[i] == -1 || dp[i] > dp[i - coins[j]] + 1) {
//递推公式
dp[i] = dp[i - coins[j]] + 1;
}
}
}
}
return dp[amount];
}
};
120. 三角形最小路径和
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
if (triangle.size() == 0) {
return 0;
}
std::vector<std::vector<int>> dp;
//初始化dp三角形
for (int i = 0; i < triangle.size(); i++) {
dp.push_back(std::vector<int>());
for (int j = 0; j < triangle[i].size(); j++) {
dp[i].push_back(0);
}
}
//初始化最后一行
for (int i = 0; i < dp.size(); i++) {
dp[dp.size()-1][i] = triangle[dp.size()-1][i];
}
for (int i = dp.size() - 2; i >= 0; i--) {
for (int j = 0; j < dp[i].size(); j++) {
//计算dp[i][j]
dp[i][j] = std::min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
}
}
return dp[0][0];
}
};
300. 最长上升子序列
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int row = nums.size();
if (row == 0) {
return 0;
}
std::vector<int> dp(row, 0);
dp[0] = 1;
int LIS = 0;
for (int i = 1; i < row; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
if (LIS < dp[i]) {
LIS = dp[i];
}
}
return LIS;
}
//利用栈
int lengthOfLIS1(vector<int>& nums) {
int row = nums.size();
if (row == 0) {
return 0;
}
std::vector<int> stack;
stack.push_back(nums[0]);
for (int i = 1; i < row; i++) {
//比栈顶元素大，push
if (nums[i] > stack.back()) {
stack.push_back(nums[i]);
} else {
for (int j = 0; j < stack.size(); j++) {
if (nums[i] <= stack[j]) {
stack[j] = nums[i];
break;
}
}
}
}
return stack.size();
}
//二分查找
int lengthOfLIS2(vector<int>& nums) {
int row = nums.size();
if (row == 0) {
return 0;
}
std::vector<int> stack;
stack.push_back(nums[0]);
for (int i = 1; i < row; i++) {
//比栈顶元素大，push
if (nums[i] > stack.back()) {
stack.push_back(nums[i]);
} else {
int pos = binary_search(stack, nums[i]);
stack[pos] = nums[i];
}
}
return stack.size();
}
//二分查找，查找比指定元素大的第一元素
int binary_search(vector<int> stack, int num) {
int start = 0;
int end = stack.size() - 1;
while (start <= end) {
int mid = start + ((end - start) >> 1);
if (num <= stack[mid]) {
if (mid == 0 || statck[mid - 1] < num) {
return mid;
}
end = mid -1;
} else {
start = mid + 1;
}
}
return -1;
}
//二分查找，查找比指定元素大的第一元素
int binary_search2(vector<int> nums, int target) {
int index = -1;
int begin = 0;
int end = stack.size() - 1;
while (index == -1) {
int mid = (begin + end) / 2;
if (target == nums[mid]) {
index = mid;
} else if (target < nums[mid]) {
if (mid == 0 || nums[mid - 1] < target) {
return mid;
}
end = mid -1;
} else if (target > nums[mid]) {
if (mid == nums.size() -1 || target < nums[mid + 1]) {
index = mid + 1;
}
begin = mid + 1;
}
}
return index;
}
};
64. 最小路径和
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if (grid.size() == 0) {
return 0;
}
int row = grid.size();
int column = grid[0].size();
std:vector<std::vector<int>> dp(row, std::vector<int>(column, 0));
dp[0][0] = grid[0][0];
//初始化第一行
for (int i = 1; i < column; i++) {
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
//从第二行开始
for (int i = 1; i < row; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
for (int j = 1; j < column; j++) {
//上边和左边选最小的 加上当前的数字
dp[i][j] = std::min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[row - 1][column - 1];
}
};
174. 地下城游戏
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
if (dungeon.size() == 0) {
return 0;
}
int row = dungeon.size();
int column = dungeon[0].size();
std::vector<std::vector<int>> dp(row, std::vector<int>(column, 0));
dp[row-1][column-1] = std::max(1, 1 - dungeon[row-1][column-1]);
//计算最后一行dp
for (int j = column - 2; j >= 0; j--) {
dp[row-1][j] = std::max(1, dp[row-1][j+1] - dungeon[row-1][j]);
}
//计算最后一列dp
for (int i = row - 2; i >=0; i--) {
dp[i][column-1] = std::max(1, dp[i+1][column-1] - dungeon[i][column-1]);
}
for (int i = row - 2; i >= 0; i--) {
for (int j = column -2; j >= 0; j--) {
//取右边或者下边最小的血量
int dp_min = std::min(dp[i][j+1], dp[i+1][j]);
dp[i][j] = std::max(1, dp_min - dungeon[i][j]);
}
}
return dp[0][0];
}
};
class Solution {
/**
* @param Integer[][] $dungeon
* @return Integer
*/
function calculateMinimumHP($dungeon) {
if (empty($dungeon)) {
return 0;
}
$row = count($dungeon);
$column = count($dungeon[0]);
$dp = [];
$dp[$row - 1][$column - 1] = max(1, 1 - $dungeon[$row - 1][$column - 1]);
//最后一行
for ($i = $column - 2; $i >= 0; $i--) {
$dp[$row - 1][$i] = max(1, $dp[$row - 1][$i + 1] - $dungeon[$row - 1][$i]);
}
//最后一列
for ($i = $row - 2; $i >= 0; $i--) {
$dp[$i][$column - 1] = max(1, $dp[$i + 1][$column - 1] - $dungeon[$i][$column - 1]);
}
for ($i = $row - 2; $i >= 0; $i--) {
for ($j = $column - 2; $j >= 0; $j--) {
$dp[$i][$j] = max(1, min($dp[$i + 1][$j], $dp[$i][$j + 1]) - $dungeon[$i][$j]);
}
}
return $dp[0][0];
}
}
关注公众号获得更多精彩文章
