首页 > 代码库 > 求不相邻金币相加和的最大值--动态规划1
求不相邻金币相加和的最大值--动态规划1
求不相邻金币相加和的最大值。
输入n个金币的金币面值(正数自定义),求这些金币不相邻和的最大值。
动态规划问题1
设f(n)为第n个金币数的最大值,f(0)=0,f(1)=a[1],输入的数组从下标为1开始。
f(n)=max{a[n]+f(n-2),f(n-1)}。
代码如下:
import java.util.Scanner; public class Jin_bi_zui_da_zhi { public static void main(String[] args) { Scanner sc=new Scanner(System.in); System.out.print("输入金币个数n:"); int n=sc.nextInt(); int a[]=new int[n+1]; System.out.print("输入n个数:"); for(int i=1;i<=n;++i) a[i]=sc.nextInt(); sc.close(); int max=hui(a,n); System.out.println("不相邻相加最大值是:"+max); }; public static int hui(int[] a,int index){ int n=a.length; int[] f=new int[n]; f[0]=0; f[1]=a[1]; for(int i=2;i<=index;++i) { int m=a[i]+f[i-2]; int max=m>f[i-1]?m:f[i-1]; f[i]=max; } return f[index]; }; }
求不相邻金币相加和的最大值--动态规划1
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。