锐客网

  1. 首页 > it技术 > >

c语言|C/JAVA 每日一练——零基础学习动态规划

javac语言动态规划

目录
?

第一题：斐波那契数列
解题思路：
代码实现
2.爬楼梯
力扣https://leetcode-cn.com/problems/climbing-stairs/
?
解题思路
代码实现：
3.使用最花费爬楼梯
解题思路：
代码详解：
java 代码详解：

第一题：斐波那契数列

c语言|C/JAVA 每日一练——零基础学习动态规划
文章图片


力扣c语言|C/JAVA 每日一练——零基础学习动态规划
文章图片
https://leetcode-cn.com/problems/fibonacci-number/
这里我们以力扣上的一道基础题来讲讲
c语言|C/JAVA 每日一练——零基础学习动态规划
文章图片

??拿到这个题目，我们首先来看题目范围，n 最多不超过 30，那是因为斐波那契数的增长速度很快，是指数级别的。所以如果 n很大，就会超过 c语言 中32位整型的范围。这是一个最基础的递推题，递推公式都已经告诉你了，我们要做的就是利用一个循环来实现这个递推。

解题思路：
  • 首先定义一个循环变量
  • 再定义一个数组记录斐波那契数列数列的第n项，并且初始化第0项和第1项
  • 然后一个for循环从第二项开始
  • 利用递推公式 f[i]=f[i-1]+f[i-2] 逐步计算每一项
  • 最后返回第n项即可
代码实现
#include 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项} }

c语言|C/JAVA 每日一练——零基础学习动态规划
文章图片

过啦！
下面附上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); }}

c语言|C/JAVA 每日一练——零基础学习动态规划
文章图片

过啦！
2.爬楼梯 力扣c语言|C/JAVA 每日一练——零基础学习动态规划
文章图片
https://leetcode-cn.com/problems/climbing-stairs/
c语言|C/JAVA 每日一练——零基础学习动态规划
文章图片
这道题跟斐波那契数列的解题思路差不多

解题思路
  • 定义一个数组f[46]，f[0]表示从第0阶爬到第i阶的方案数
  • 每次可以爬一层也可以爬两层，对于第i阶楼梯来说 要么是从第[i-1]阶爬上来的，要么是从第[i-2]阶爬过来的
  • 递推公式 f[i]=f[i-1]+f[i-2]
代码实现：
#include 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]; } }

c语言|C/JAVA 每日一练——零基础学习动态规划
文章图片

过啦！
下面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]; } } }

c语言|C/JAVA 每日一练——零基础学习动态规划
文章图片

过啦！
3.使用最花费爬楼梯力扣c语言|C/JAVA 每日一练——零基础学习动态规划
文章图片
https://leetcode-cn.com/problems/min-cost-climbing-stairs/
c语言|C/JAVA 每日一练——零基础学习动态规划
文章图片


解题思路：
这道题跟上道题 特别相似 就是改成了计算最小花费
我们用一个数组来表示状态 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 int main(){ int min(int a , int b){ //为了求最小值 我们之间用c语言的条件运算符就行啦 return a

c语言|C/JAVA 每日一练——零基础学习动态规划
文章图片

过啦！
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

c语言|C/JAVA 每日一练——零基础学习动态规划
文章图片

过啦！
以上就是小王同学给大家准备的三道比较基础的动态规划入门题
今天 元宵节小王同学在这里 祝友友们 节日快乐
记得一定要出汤圆哦（doge）
如果觉得小王同学的文章 对你们有帮助的话
麻烦给个三连吧 ！！
?????????????????????
【c语言|C/JAVA 每日一练——零基础学习动态规划】

    推荐阅读


    上一篇：c语言|C语言——结构体（初阶版）

    下一篇：Spring 创建对象的方式