C/JAVA 每日一练——零基础学习动态规划
目录
力扣https://leetcode-cn.com/problems/climbing-stairs/
第一题:斐波那契数列
https://leetcode-cn.com/problems/fibonacci-number/
这里我们以力扣上的一道基础题来讲讲
拿到这个题目,我们首先来看题目范围,n 最多不超过 30,那是因为斐波那契数的增长速度很快,是指数级别的。所以如果 n 很大,就会超过 c语言 中32位整型的范围。这是一个最基础的递推题,递推公式都已经告诉你了,我们要做的就是利用一个循环来实现这个递推。
解题思路:
- 首先定义一个循环变量
- 再定义一个数组记录斐波那契数列数列的第n项,并且初始化第0项和第1项
- 然后一个for循环从第二项开始
- 利用递推公式 f[i]=f[i-1]+f[i-2] 逐步计算每一项
- 最后返回第n项即可
代码实现
#include<stdio.h>
int main(){
int fib(int n){
int f[35]={0,1};//第0项和第一项 分别为 0和1
for(int i = 2;i<=n;i++){ //从第二项开始遍历
f[i]=f[i-1]+f[i-2]; //递推公式
}
return f[n]; //最后返回第n项
}
}
过啦!
下面附上java代码实现:
class Solution {
public int fib(int n) {
if(n==0){
return 0;
}
else if(n==1){
return 1;
}
return fib(n-1)+fib(n-2);
}
}
过啦!
2.爬楼梯
力扣
https://leetcode-cn.com/problems/climbing-stairs/
这道题跟斐波那契数列的解题思路差不多
解题思路
- 定义一个数组f[46],f[0]表示从第0阶爬到第i阶的方案数
- 每次可以爬一层也可以爬两层,对于第i阶楼梯来说 要么是从第[i-1]阶爬上来的,要么是从第[i-2]阶爬过来的
- 递推公式 f[i]=f[i-1]+f[i-2]
代码实现:
#include<stdio.h>
int main(){
int climbStairs(int n){
int f[46]={1,1};
for(int i = 2;i<=n;i++){
f[i]=f[i-1]+f[i-2];
}
return f[n];
}
}
过啦!
下面java代码详解:
class Solution {
public int climbStairs(int n) {
//dp[n]表示n道楼梯有几种爬的方法
if(n == 1){
return 1;
}
else if(n == 2){
return 2;
}
else{
int [] dp=new int [n+1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for(int i = 3;i <= n;++i){
dp[i] = dp[i-1]+dp[i-2];//经过一步到第i道楼梯与经过两步到i道楼梯的方法数之和
}
return dp[n];
}
}
}
过啦!
3.使用最花费爬楼梯
https://leetcode-cn.com/problems/min-cost-climbing-stairs/
解题思路:
这道题跟上道题 特别相似 就是改成了计算最小花费 我们用一个数组来表示状态 f[i]表示爬到第i层所花费的状态 但是题目要求 每次只能爬一个或两个台阶 所以这里的f[i]这个状态只能从f[i-1]或者f[i-2]转移过来 1.如果从i-1 爬上来 那么花费就是f[i-1]+cost[i-1] 2.如果从i-2爬上来 那么花费就是f[i-2]+cost[i-2] 我们要求的是最小花费 也就是f[i]=min(f[i−1]+cost[i−1],f[i−2]+cost[i−2]) 考虑一下初始情况 f[0]和f[1]这里都是0;
代码详解:
#include<stdio.h>
int main(){
int min(int a , int b){ //为了求最小值 我们之间用c语言的条件运算符就行啦
return a<b?a:b;
}
int minCostClimbingStairs(int* cost, int costSize){
int f[1001]={0,0}; //定义一个数组 f[i]从第0阶到第i阶花费的费用,并且初始化 第0项和第1项
for(int i = 2;i<=costSize;i++){
f[i]= min (f[i-1]+cost[i-1],f[i-2]+cost[i-2]);//套用公式
}
return f[costSize]; //返回第n项
}
}
过啦!
java 代码详解:
class Solution {
public int minCostClimbingStairs(int[] cost) {
int []dp =new int[cost.length+1]; //cost.length+1 i下标就能对应台阶数了
dp[1]=cost[0]; //这里的dp[0]不用,从1开始数
//i表示第几号台阶,dp[i]就表示上这号台阶吃的最少的费用
dp[2]=cost[1];
for(int i=3;i<dp.length;i++){
// // 因为可以跨一步或两步,因此可以从前一个台阶,或前两个台阶上来
// 到本层台阶需要吃本层台阶的屎,又因为这个i是用来遍历dp数组的
// 而dp数组长度比cost数组长1,所以用i从cost数组中取值要减1
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-1]);
}
return min(dp[cost.length],dp[cost.length-1]);
}
public int min(int a,int b){ //为了实现最小值 这里我们用一个最小值的函数来实现
return a<b?a:b;
}
}
过啦!
以上就是小王同学给大家准备的三道比较基础的动态规划入门题
今天 元宵节 小王同学在这里 祝友友们 节日快乐
记得一定要出汤圆哦(doge)
相关文章
- Java桥方法
- java笔试题_一道简单的 Java 笔试题,但值得很多人反思
- 说一下java的运行机制_Java运行机制是什么?「建议收藏」
- java图书馆新地址_最受Java开发者喜爱的5款开源IDE盘点
- Java学习day086 部署Java程序(三)(applet:一个简单的applet、applet HTML标记属性、使用参数向applet传递信息)
- java actioncontext_关于struts2中ActionContext的实现原理
- Java 零拷贝_java高性能编程
- java分页代码_基本分页存储管理java代码
- Java学习笔记 (继承、this、super)
- java学习深度优先算法详解编程语言
- Java开发之文件上传详解编程语言
- Linux下配置Java环境变量的简易指南(linux配置java环境变量)
- Java连接MySQL:实现数据库操作(java中连接mysql)
- Java面试中的Redis题目剖析(java面试题redis)
- 合Java与Oracle联手打造崭新未来(java和oracle联)
- Java和Oracle技术融合,汇聚智能新大陆(java oracle包)
- 本使用Oracle Java 进行升级新版本带来新体验(oracle java版)
- Java常用排序算法及性能测试集合
- Java基础之java处理ip的工具类