斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
思路：
无需多盐，这，就是最简单的动归！
代码如下：
class Solution {
public:
int fib(int n) {
vector<int> F(n + 1);
if (n < 1)
return 0;
F[0] = 0;
F[1] = 1;
for (int i = 2; i <= n; i++) {
F[i] = F[i - 1] + F[i - 2];
}
return F[n];
}
};
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2：
输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
思路：
dp[i]： 爬到第i层楼梯，有dp[i]种方法。
i-1有一种方法（一次爬1阶）到i。
i-2有一种方法(一次爬两阶）到i。（一次爬一阶是到i-1，包含在dp[i-1]里面了）
那dp[i]=dp[i-1]+dp[i-2]。
和斐波那契数列一样，代码如下：
class Solution {
public:
int climbStairs(int n) {
vector<int> dp(n + 1);
if (n <= 1)
return 1;
// 令dp[n]=n,dp[n]=dp[n-1]+dp[n-2]
dp[0] = 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 ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。 - 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。
示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1] 输出：6 解释：你将从下标为 0 的台阶开始。 - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。 - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。 - 支付 1 ，向上爬一个台阶，到达楼梯顶部。 总花费为 6 。
思路：
dp[i]是最低花费，dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])。
ez，代码如下：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
// dp[i]是最低花费
// dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
vector<int> dp(cost.size() + 1);
if (cost.size() < 1)
return 0;
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= cost.size(); i++) {
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[cost.size()];
}
};
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7 输出：28
示例 2：
输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3 输出：28
示例 4：
输入：m = 3, n = 3 输出：6
思路：
dp[m][n]是路径和， dp[m][n]=dp[m][n-1]+dp[m-1][n]。
要注意的是m,n是从0开始的，所以终点是在[m-1][n-1]上。
同时初始化的时候要把第一行和第一列初始化了，因为递推公式无法求m[0-1]（或n[0-1])。
代码如下：
class Solution {
public:
int uniquePaths(int m, int n) {
// dp[m][n]是路径和
// dp[m][n]=dp[m][n-1]+dp[m-1][n];
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
dp[0][0] = 0;
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
};
给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。
网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
返回机器人能够到达右下角的不同路径数量。
测试用例保证答案小于等于 2 * 109。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]] 输出：1
思路：
基本与上题一样，但在初始化时要注意：一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作，dp[0][j]同理。
代码如下：
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
// 创建 dp 数组，初始化为 0
vector<vector<int>> dp(m, vector<int>(n, 0));
// 如果起点有障碍，则路径为 0
if (obstacleGrid[0][0] == 1) return 0;
// 初始化第一列
for (int i = 0; i < m; i++) {
if (obstacleGrid[i][0] == 1) break; // 如果遇到障碍，后续路径无法到达
dp[i][0] = 1;
}
// 初始化第一行
for (int i = 0; i < n; i++) {
if (obstacleGrid[0][i] == 1) break; // 如果遇到障碍，后续路径无法到达
dp[0][i] = 1;
}
// 填充 dp 数组
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
dp[i][j] = 0; // 如果当前位置有障碍，路径为 0
} else {
dp[i][j] = dp[i-1][j] + dp[i][j-1]; // 否则路径数为从上方和左方的路径之和
}
}
}
// 返回右下角的路径数
return dp[m-1][n-1];
}
};
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
思路：
最大乘积为dp[i]，dp[i] = max(dp[i], max((i – j) * j, dp[i – j] * j))；
代码如下：
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n + 1);
dp[2] = 1;
for (int i = 3; i <= n ; i++) {
for (int j = 1; j <= i / 2; j++) {
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
}
}
return dp[n];
}
};
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3 输出：5
示例 2：
输入：n = 1 输出：1
思路：
dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。
dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
初始化dp[0] = 1
代码如下：
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n + 1);
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
};
暂无评论