leetcode刷题记录——动态规划
leetcode刷题记录——动态规划
509、斐波那契数
和爬楼梯一样，最基础的动态规划，没什么好说的。
class Solution
{
public:
int fib(int n)
{
if (n == 0)
{
return 0;
}
vector<int> dp(3, 0);
dp[1] = 1;
dp[2] = 1;
for (size_t i = 2; i < n + 1; i++)
{
dp[2] = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = dp[2];
}
return dp[2];
}
};1137、第N个泰波那契数
略
class Solution
{
public:
int tribonacci(int n)
{
vector<int> dp(4);
dp = {0, 1, 1, 2};
if (n <= 3)
{
return dp[n];
}
for (size_t i = 3; i < n + 1; i++)
{
dp[3] = dp[0] + dp[1] + dp[2];
dp[0] = dp[1];
dp[1] = dp[2];
dp[2] = dp[3];
}
return dp[3];
}
};740、删除并获得点数
首先找到数组 nums 中的最大元素值 maxNum。然后创建一个长度为 maxNum + 1 的数组 dp，用于记录删除元素值的获得的分数。
两个变量 prev 和 curr，分别表示前一个元素值的最大点数和当前元素值的最大点数。因为删除 nums[i] 之后，必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素，所以遍历dp数组，当前最大得分为 prev和删除当前元素所得分之和与删除前一元素所得分 之间的更大值，这样，经过遍历后，curr 将会记录整个数组中的最大点数。
class Solution
{
public:
int deleteAndEarn(vector<int> &nums)
{
int maxNum = *max_element(nums.begin(), nums.end());
vector<int> dp(maxNum + 1, 0);
for (int num : nums)
{
dp[num] += num;
}
int prev = 0;
int curr = 0;
for (int i = 1; i <= maxNum; i++)
{
int temp = curr;
curr = max(prev + dp[i], curr);
prev = temp;
}
return curr;
}
};62、不同路径
二维数组 dp，大小为 m × n，用于存储到达每个网格位置的不同路径数。初始时，所有元素都被初始化为 0。将起始位置 (0, 0) 的路径数设为 1，表示只有一条路径可以到达起始位置。定义一个方向数组 dirs，其中包含两个方向的偏移量：{-1, 0} 和 {0, -1}。这两个方向表示向上和向左移动。
使用两个嵌套的循环遍历所有的网格位置 (i, j)，其中 i 表示行索引，j 表示列索引。在每个网格位置 (i, j)，使用一个额外的内部循环遍历方向数组 dirs 中的两个方向。对于每个方向 (dx, dy)，计算新的位置 (i + dx, j + dy)。然后检查新位置是否在合法范围内（即行索引和列索引都大于等于 0），如果合法，则将当前网格的路径数加上新位置的路径数，即 dp[i][j] += dp[i + dx][j + dy]。最后，返回 dp[m - 1][n - 1]，即到达目标位置 (m - 1, n - 1) 的不同路径数。
class Solution
{
public:
int uniquePaths(int m, int n)
{
vector<vector<int>> dp(m, vector<int>(n, 0));
dp[0][0] = 1;
vector<pair<int, int>> dirs =
{{-1, 0}, {0, -1}};
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
for (size_t k = 0; k < 2; k++)
{
if (i + dirs[k].first >= 0 && j + dirs[k].second >= 0)
{
dp[i][j] += dp[i + dirs[k].first][j + dirs[k].second];
}
}
}
}
return dp[m - 1][n - 1];
}
};64、最小路径和
使用三重循环来遍历网格中的每个位置。外层两个循环分别用于遍历行和列，内层循环用于遍历向上和向左两个方向。
在内层循环中，首先判断当前位置 (i, j) 是否可以向上或向左移动。如果可以移动（即不越界），则使用 MIN 宏比较当前位置的最小路径和 dp[i][j] 和上方或左方位置的最小路径和 dp[i + dir[k].first][j + dir[k].second] 的和加上当前位置的值 grid[i][j] 的大小，并将较小的值赋给 dp[i][j]。
#define MIN(x, y) x > y ? y : x
class Solution
{
private:
vector<pair<int, int>> dir = {
{-1, 0},
{0, -1},
};
public:
int minPathSum(vector<vector<int>> &grid)
{
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
dp[0][0] = grid[0][0];
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
for (int k = 0; k < 2; k++)
{
if (i + dir[k].first >= 0 &&
j + dir[k].second >= 0)
{
dp[i][j] = MIN(dp[i][j],
dp[i + dir[k].first][j + dir[k].second] + grid[i][j]);
}
}
}
}
return dp[m - 1][n - 1];
}
};------本页内容已结束，喜欢请分享------
腾讯云开发者
