public class SplitMoney { int[][] table = new int[5][3001]; public static void main(String[] args) { int[] arr = new int[]{5,10,25,1}; int aim = 3000;
        SplitMoney splitMoney = new SplitMoney(); long time1= System.currentTimeMillis();
        System.out.println(splitMoney.splitSearchTable(arr,0,aim)); long time2= System.currentTimeMillis();
        System.out.println("search table method time (ms):"+(time2-time1));

        time1= System.currentTimeMillis();
        System.out.println(splitMoney.splitRecursive(arr, 0, aim));

        time2= System.currentTimeMillis();

        System.out.println("recursive method time (ms):"+(time2-time1));


    } public int splitRecursive(int[] arr,int start,int aim){ if(arr==null|| arr.length==0 || aim<=0){ return 0;
        } return splitProcess(arr,start,aim);
    } public int splitProcess(int[] arr,int start,int aim){ int sum =0; if(aim==0){ return 1;
        } if(start==arr.length){ return 0;
        } else{ while(aim>=0){
                sum+=splitProcess(arr, start + 1, aim);
                aim = aim-arr[start];
            }
        } return sum;
    } public int splitSearchTable(int[] arr,int start,int aim){ if(arr==null|| arr.length==0 || aim<=0){ return 0;
        } return splitProcess1(arr, start, aim);
    } public int splitProcess1(int[] arr,int start,int aim){ int sum =0; if(aim==0){ table[start][aim]=1; return 1;
        } if(start==arr.length){ return 0;
        } else{ while(aim>=0){ if(table[start][aim]!=0){
                    sum += table[start][aim];
                } else {
                    sum += splitProcess1(arr, start + 1, aim);
                }
                aim -=arr[start];
            }
        } if(aim>=0){ table[start][aim] = sum;
        } return sum;
    }


}