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];
}
};120、三角形的额最小路径和
对于当前遍历到的元素 triangle[i][j]，计算它的最小路径和。首先，初始化 upper 为一个较大的值 INT_MAX，表示当前元素的上方路径和的初始值。如果当前元素不是当前行的最后一个元素（即 j != triangle[i].size() - 1），则将 upper 更新为上方路径和的右上方元素 triangle[i - 1][j]。如果当前元素的索引 j - 1 大于等于 0，说明当前元素有左上方元素，将 upper 更新为上方路径和的左上方元素 triangle[i - 1][j - 1] 和当前的 upper 中的较小值。将当前元素的值更新为当前元素的值加上 upper，表示当前元素的最小路径和。如果当前行是最后一行（即 i == row - 1），更新 ret 为当前元素的最小路径和和 ret 中的较小值。
class Solution
{
public:
int minimumTotal(vector<vector<int>> &triangle)
{
int row = triangle.size();
int ret = triangle[0][0];
for (int i = 1; i < row; i++)
{
ret = INT_MAX;
for (int j = 0; j < triangle[i].size(); j++)
{
int upper = INT_MAX;
if (j != triangle[i].size() - 1)
{
upper = triangle[i - 1][j];
}
if (j - 1 >= 0)
{
upper = min(upper, triangle[i - 1][j - 1]);
}
triangle[i][j] += upper;
if (i == row - 1)
{
ret = min(ret, triangle[i][j]);
}
}
}
return ret;
}
};
