public class HelloWorld {
public static void main(String[] args) {
}
/**
* 机器人走格子
* (x,y) 表示目标点，只能向右或者向下走
* 题目大意就是求(0,0)到(x,y)有多少种走法
* f(x,y)=f(x-1,y)+f(x,y-1);
*/
// 递归版本
static int solve(int x,int y){
if(x==1||y==1) return 1;
return solve(x-1,y)+solve(x,y-1);
}
// 迭代版
// m 表示行数，n 表示列数
static int solve1(int m,int n){
int[][] map = new int[m+1][n+1];
//将第二行全置1
for (int i=1;i<=n ;i++ ){
map[1][i] =1;
}
// 将第二列全置1
for (int j=1;j<=m ;j++ ){
map[j][1] =1;
}
//利用递推公式赋值
for (int i=2;i<=m ;i++ ){
for (int j=2;j<=n ;j++ ){
map[i][j] = map[i-1][j]+map[i][j-1];
}
}
return map[m][n];
}
/**
* 硬币面值问题
* 给定 1 5 10 25 求 n 组合种数
*
* 思路：递推无法解决，只能进行枚举，而枚举思路先从大面值开始取，
* 算出大面值可举次数，然后依次递归选取小面值
*/
static int countWays(int n){
if(n<=0) return 0;
//面值数组
int[] value ={1,5,10,25};
return countWaysCore(n,value,value.length-1);
}
// cur 表示 所取面值数组下标
static int countWaysCore(int n,int[] coins,int cur){
if(cur ==0) return 1;
int result = 0;
int counts_cur = n/coins[cur];//n 在当前面值下可选择次数
for (int i=0;i<=counts_cur ;i++ ){
int last = n-i*coins[cur];
result = result + countWaysCore(last,coins,cur-1);
}
return result;
}
}