网站联系方式设置要求,上海门户网站论坛,wordpress调用多媒体,网站收录地址理论基础
文章 说实话#xff0c;没做过题连理论基础都看不懂 1 确定dp数组#xff08;dp table#xff09;以及下标的含义 2 确定递推公式 3 dp数组如何初始化 4 确定遍历顺序 5 举例推导dp数组
这道题目我举例推导状态转移公式了么#xff1f; 我打印dp数组的日志了么没做过题连理论基础都看不懂 1 确定dp数组dp table以及下标的含义 2 确定递推公式 3 dp数组如何初始化 4 确定遍历顺序 5 举例推导dp数组
这道题目我举例推导状态转移公式了么 我打印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 示例 2
输入3 输出2 解释F(3) F(2) F(1) 1 1 2 示例 3
输入4 输出3 解释F(4) F(3) F(2) 2 1 3 提示
0 n 30
题目简单用于理解动态规划
class Solution {
public:int fib(int N) {if (N 1) return N;int dp[2];dp[0] 0;dp[1] 1;for (int i 2; i N; i) {int sum dp[0] dp[1];dp[0] dp[1];dp[1] sum;}return dp[1];}
};当然可以用递归的方法
70. 爬楼梯
文章
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
注意给定 n 是一个正整数。
示例 1
输入 2 输出 2 解释 有两种方法可以爬到楼顶。 1 阶 1 阶 2 阶 示例 2
输入 3 输出 3 解释 有三种方法可以爬到楼顶。 1 阶 1 阶 1 阶 1 阶 2 阶 2 阶 1 阶
想不出来啊 到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来那么就可以想到动态规划了。 dp[i] 爬到第i层楼梯有dp[i]种方法 class Solution {
public:int climbStairs(int n) {if (n 1) return n;int dp[3];dp[1] 1;dp[2] 2;for (int i 3; i n; i) {int sum dp[1] dp[2];dp[1] dp[2];dp[2] sum;}return dp[2];}
};746. 使用最小花费爬楼梯
文章讲解 数组的每个下标作为一个阶梯第 i 个阶梯对应着一个非负数的体力花费值 cost[i]下标从 0 开始。
每当你爬上一个阶梯你都要花费对应的体力值一旦支付了相应的体力值你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时你可以选择从下标为 0 或 1 的元素作为初始阶梯。
示例 1
输入cost [10, 15, 20] 输出15 解释最低花费是从 cost[1] 开始然后走两步即可到阶梯顶一共花费 15 。 示例 2
输入cost [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出6 解释最低花费方式是从 cost[0] 开始逐个经过那些 1 跳过 cost[3] 一共花费 6 。 提示
cost 的长度范围是 [2, 1000]。 cost[i] 将会是一个整型数据范围为 [0, 999]
能想到由前两步推但是没太象具体不打算走非min的步了其实不对。 还是要按照步骤来 min(dp1 cost[i - 1], dp0 cost[i - 2])
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int dp0 0;int dp1 0;for (int i 2; i cost.size(); i) {int dpi min(dp1 cost[i - 1], dp0 cost[i - 2]);dp0 dp1; // 记录一下前两位dp1 dpi;}return dp1;}
};
