一、爬楼梯
题目：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
思路：
此题目和铺地板等题目一样，都有两种方式解决。
①递归：递归思路为不断递归方法,求F(i)时候就要求F(i-1)和F(i-2);
②动态规划：规划方程F(i)=F(i-1)+f(i-2)；(i从2开始)
动态规划具体实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| import java.util.Scanner;
public class FeiBoNaQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt(); //定义数组的长度
int[] a=new int[n];
a[0]=1; //要爬一层台阶，有一种方法
a[1]=2; //要爬两层台阶，有两种方法
System.out.println(climbStairs(n,a)); //传递a数组和要爬的层数
}
public static int climbStairs(int n,int[] a) {
if(n==1)
return 1; //如果爬一层楼就是1个方法
for(int i=2;i<n;i++)
{
a[i]=a[i-1]+a[i-2]; //相当于斐波拉契数列思想
}
return a[n-1]; //返回的一定是数组长度-1的值
}
}
|
代码结果如下：
！
二、买卖股票的最佳时机
题目：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
例如：
输入：7,1,5,3,6,4
输出: 5
解释：在第二天的时候买入，在第五天卖出，最大利润=6-1=5。
注意利润不能是7-1=6，因为卖出价格需要大于买入价格。
思路：
①拿到题目第一种思路就是暴力求解法，利用两重循环两个数进行比较，然后根据条件限制选出两个数值之间差距最大的两个数，即为买卖股票的最佳时机。
具体实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| import java.util.Scanner;
public class FeiBoNaQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
for(int i=0;i<a.length;i++)
{
a[i]=input.nextInt();
}
System.out.println(maxProfit(a));
}
public static int maxProfit(int[] a) {
int max=0;
for(int i=0;i<a.length;i++)
{
for(int j=i+1;j<a.length;j++)
{
if(j>=i) //后面的那个价格要比前面的高（保证不亏钱）
{
max=Math.max(max,(a[j]-a[i])); // 选出两者之间差距最大的即为最大利润
}
}
}
return max;
}
}
|
代码结果如下：
！
②第二种思路就是动态规划，这还是我参考别人的想法想到了。
当前的最大利润=max{前一个值的最大利润max,当前值-前面的最小值}。
max=Math.max(max,(a[i]-min)); （min初始值一定要为a[0],不然默认为0的话,最大利润永远为0）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| import java.util.Scanner;
public class TouQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
for(int i=0;i<a.length;i++)
{
a[i]=input.nextInt();
}
System.out.println(rob(a));
}
public static int rob(int[] a) {
int max=0,min=a[0],i=0; //先让最小值为第一个值
for( i=0;i<a.length;i++)
{
min=Math.min(min,a[i]); //每次判断确定最小值
max=Math.max(max,(a[i]-min)); //判断当前的最大利润是前一个的利润还是当前减去前面的最小值哪个大
}
return max;
}
}
|
代码结果如下：
！
三、买卖股票的最佳时机II
题目：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例：
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
思路：
①可以发现只要后边的值大于前面的值(上升状态)：上升点(买入)到上升的最高点(卖出)就是获得的利润，然后计算总和所有的上升状态就可以得到最大利润。
具体实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| import java.util.Scanner;
public class TouQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
for(int i=0;i<a.length;i++)
{
a[i]=input.nextInt();
}
System.out.println(rob(a));
}
public static int rob(int[] a) {
int i=0,sum=0;
for(i=1;i<a.length;i++)
{
if(a[i-1]<a[i]) //上升状态
{
sum+=a[i]-a[i-1]; //将所有上升状态的值都加起来
}
}
return sum;
}
}
|
代码结果如下：
四、打家劫舍
题目：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例：
输入：2,7,9,3,1
输出：12
解释：先偷第一家的金额为2，然后偷第三家的金额为9，接着偷第五家的金额为1.
思路：
此题为经典的动态规划问题，我一开始理解的就是要么奇数最大要么偶数最大就解决了，然后我就循环判断奇数总和与偶数总和的大小，但是发现还是有很大问题。
以三个为例：
第一步：我们只偷第一家的，记作max=a[0];
第二步：因为不能偷相邻的房间，我们要判断是第一家的还是第二家的金额大，记作max=Math.max(a[0],a[1]);
第三步：考虑是第一家的金额+第三家的金额和第二家的金额那个大，记作max=Math.max(a[0]+a[2],a[1]);
由此,我们可以用一个a数组存放输入的每家金额值，b数组去存放每一步取得的最大的金额：
b[i]=Math.max((b[i-2]+a[i]),b[i-1]);
具体实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| import java.util.Scanner;
public class TouQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
for(int i=0;i<a.length;i++)
{
a[i]=input.nextInt();
}
System.out.println(rob(a));
}
public static int rob(int[] a) {
int[] b=new int[a.length];
b[0]=a[0]; //只能偷第一家
b[1]=Math.max(a[0],a[1]); //确定偷第二家的时候是哪一家比较有钱，确定从1还是2家开始
for(int i=2;i<a.length;i++)
{
b[i]=Math.max(b[i-2]+a[i],b[i-1]); //比较前一家的金额和之前一家加上现在一家的金额哪个大
}
return b[a.length-1]; //注意输出长度-1的值
}
}
|
代码结果如下：
