想请教各位小伙伴,得物笔试遇到一道编程题,笔试后写出了代码,但现在没法验证代码的正确性,能帮我看一下我的思路对吗?或者有其他更好的解法吗?图片分别是代码和思路,另外附上源程序。万分感谢!
题目描述:
即将进入假期的小A打算做很多homework,因为小A每天的心情不同,所以他每天可以做的homework数量可能不同。聪明的小A知道一直做homework是对身体不好的,所以需要他给自己制订一份劳逸结合的假期homework计划,也就是在每次做homework后都需要休息1天或2天(不能不休息,也不能休息大于2天) 再继续做homework。爱学习的小A决定在假期的第1天或第2天开始做homework,那么他在假期内最多能做多少homework?
输入描述:
第一行有1个正整数n,表示假期的天数
第二行有n个正整数ai,表示小A每天能完成的homework数,
1<=n<=10000,0<=ai<=10000
示例输入1:
5
2,1,2,1,2
示例输出1:
6
示例输入2:
8
2,1,2,1,2,1,2,3
示例输出2:
9
以下是我写的代码:
public class homework {
public static void main(String[] args) {
int [] values = {2,1,2,1,2,1,2,1}; int n = 8;
// 预期的 output: 8
System.out.println(f(n, values));
}
public static int f(int index, int []v){
if (index == 0) return 0;
if (index == 1) return v[0];
if (index == 2) return Math.max(v[0],v[1]);
int p1 = Math.max(f(index-3, v),f(index -2, v))+ v[index-1]; // p1: 第 index天写homework
int p2 = Math.max(f(index-2, v),f(index-1, v)); // p2: 第 index天休息
return Math.max(p1,p2);
}
}
以下是我的思路:
/** 思路分析:
* 函数f(int index)的含义:在index天的假期里,最多能完成的作业数为 f(index)。
* 从后往前考虑,先考虑假期最后一天,即第index天,是否工作或休息,
* 举例,求5天的假期最多能完成多少作业,
* 先假设第 5天休息了并且第 4天也休息了,第 3天必须写作业,同时还剩3天,这种情况相当于求3天的假期最多能完成多少作业;
* 那么“求5天假期最多完成的作业数”的问题就转化为 “求3天假期最多完成的作业数”这一子问题!
* 感觉我写的以上的函数含义存在问题,求大佬指正。
*
* 考虑假期最后一天,即第index天,是否工作或休息,存在两种情况,如下所示:
* 一、假设 ”第 index 天做作业“,那么第 index-1 天必然休息,下面存在两种可能:
* 1) 第 index-2 天也休息了 ---> 那么第 index-3天必须工作 ===> 此刻,f(index) = v[index-1]+f(index-3)
* 2) 第 index-2 天做作业了 ===> 此刻,f(index) = v[index-1]+f(index-2)
* 综上,p1 = f‘(index) = Math.max(f(index-3),f(index-2))+v[index-1]
* 二、假设 ”第 index 天休息“,下面也存在两种可能:
* 1) 第 index-1 天也休息了(连休两天) ---> 那么第 index-2天必须工作 ===> 此刻,f(index) = f(index-2)
* 2) 第 index-1 天做作业了 ===> 此刻,f(index) = f(index-1)
* 综上,p2 = f‘’(index) = Math.max(f(index-2),f(index-1))
* 所以,可以得出总的表达式;
* f(index) = Math.max(p1, p2);
**/