中国轻工建设公司网站,lol怎么做直播网站,江西网站建设哪家好,dw2021网页设计教程有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]#xff0c;得到的价值是value[i] 。每件物品只能用一次#xff0c;求解将哪些物品装入背包里物品价值总和最大。 步骤分为以下五步#xff1a;
确定dp数组#xff08;dp table#xff09;以及下标的含… 有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。 步骤分为以下五步
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
509. 斐波那契数 斐波那契数通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是 F(0) 0F(1) 1 F(n) F(n - 1) F(n - 2)其中 n 1 给你n 请计算 F(n) 。 示例 1 输入2输出1解释F(2) F(1) F(0) 1 0 1 int fib(int n){if(n1){return n;}int dp[n1];dp[0]0;dp[1]1;for(int i2;in;i){dp[i]dp[i-1]dp[i-2];}return dp[n];
}
70. 爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢 注意给定 n 是一个正整数。 示例 1 输入 2输出 2 dp[i] 爬到第i层楼梯有dp[i]种方法 首先是dp[i - 1]上i-1层楼梯有dp[i - 1]种方法那么再一步跳一个台阶不就是dp[i]。 然后是dp[i - 2]上i-2层楼梯有dp[i - 2]种方法那么再一步跳两个台阶不就是dp[i]。 那么dp[i]就是 dp[i - 1]与dp[i - 2]之和。 递推公式dp[i] dp[i - 1] dp[i - 2]
int climbStairs(int n) {if(n1){return n;}int dp[n1];dp[1]1;dp[2]2;for(int i3;in;i){dp[i]dp[i-1]dp[i-2];}return dp[n];
} 这道题目还可以继续深化就是一步一个台阶两个台阶三个台阶直到 m个台阶有多少种方法爬到n阶楼顶。 只需要将第二个循环中的2换成m就能用于其他题。
class Solution {
public:int climbStairs(int n) {vectorint dp(n1,0);dp[0]1;for(int i1;in;i){for(int j1;j2;j){if(i-j0) dp[i]dp[i-j];}}return dp[n];}
};
746. 使用最小花费爬楼梯 数组的每个下标作为一个阶梯第 i 个阶梯对应着一个非负数的体力花费值 cost[i]下标从 0 开始。每当你爬上一个阶梯你都要花费对应的体力值一旦支付了相应的体力值你就可以选择向上爬一个阶梯或者爬两个阶梯。请你找出达到楼层顶部的最低花费。在开始时你可以选择从下标为 0 或 1 的元素作为初始阶梯。 示例 1 输入cost [10, 15, 20]输出15解释最低花费是从 cost[1] 开始然后走两步即可到阶梯顶一共花费 15 。 int minCostClimbingStairs(int* cost, int costSize) {int dp[costSize1];dp[0]0;dp[1]0;for(int i2;icostSize;i){dp[i]fmin(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);}return dp[costSize];
}
