Java题目训练——跳台阶扩展问题和快到碗里来

目录

一、跳台阶扩展问题

二、快到碗里来

一、跳台阶扩展问题

题目描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

数据范围：1<=n<=20

进阶：空间复杂度O(1) ， 时间复杂度O(1)

示例 

示例1

输入：3

输出： 4

示例2

输入：1

输出： 1

题目解析：

本题使用动态规划的思想，首先，求状态方程：

记当跳上第n阶台阶的时候的状态是f(n)，则

f(n) = f(n - 1) + f(n - 2) + f(n - 3) + ... + f(1) + f(0)

记当跳上第 n - 1 阶台阶的时候的状态是f(n - 1)，则

f(n - 1) = f(n - 2) + f(n - 3) + f(n - 4) + ... + f(1) + f(0)

可以得到

f(n) - f(n - 1) = f(n - 1)

f(n) = 2 * f(n - 1)

状态方程为：f(n) = 2 * f(n - 1)

初始状态：f(1) = 1

循环遍历通过状态方程求得f(number)即可。

import java.util.*;
public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param number int整型* @return int整型*/public int jumpFloorII (int number) {if(number == 1){return 1;}if(number == 2){return 2;}//动态规划//f(n) = f(n - 1) + f(n - 2) + f(n - 3) + ... + f(1) + f(0)//f(n - 1) =f(n - 2) + f(n - 3) + f(n - 4) + ... + f(1) + f(0)//f(n) - f(n - 1) = f(n - 1)//f(n) = 2 * f(n - 1)int[] dp = new int[number + 1];dp[0] = 0;dp[1] = 1;dp[2] = 2;for (int i = 3; i <= number; i++) {dp[i] = dp[i - 1] * 2;}return dp[number];}
}

二、快到碗里来

题目描述：

小喵们很喜欢把自己装进容器里的（例如碗），但是要是碗的周长比喵的身长还短，它们就进不去了。 现在告诉你它们的身长，和碗的半径，请判断一下能否到碗里去。

输入描述：

输入有多组数据。

每组数据包含两个整数n (1≤n≤2^128) 和r (1≤r≤2^128)，分别代表喵的身长和碗的半径。 圆周率使用3.14。

输出描述：

对应每一组数据，如果喵能装进碗里就输出“Yes”；否则输出“No”。

示例

输入：6 1

           7 1

           9876543210 1234567890

输出：Yes

           No

           No

题目解析：

        本题就是一个简单的问题，首先根据半径求圆的周长，然后比较周长和身长输出相应结果即可，需要注意是数据范围，如果用整型可能会超出范围，所以这里用了double 类型。

import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNext()){double n = scanner.nextDouble();double r = scanner.nextDouble();isBowl(n, r);}}public static void isBowl(double n, double r){double len = 3.14 * 2 * r;if(n < len){System.out.println("Yes");}else{System.out.println("No");}}
}

如有建议或想法，欢迎一起讨论学习~