求不相邻金币相加和的最大值。

  输入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];};}