步骤：
1)找到什么可变参数可以代表一个递归状态，也就是哪些参数一旦确定，返回值就确定了
2)把可变参数的所有组合映射成一张表，有 1 个可变参数就是一维表，2 个可变参数就
是二维表，......
3)最终答案要的是表中的哪个位置，在表中标出
4)根据递归过程的 base case，把这张表的最简单、不需要依赖其他位置的那些位置填好
值
5)根据递归过程非base case的部分，也就是分析表中的普遍位置需要怎么计算得到，那
么这张表的填写顺序也就确定了
6)填好表，返回最终答案在表中位置的值
2.看题：
机器人达到指定位置方法数 假设有排成一行的 N 个位置，记为 1~N，N 一定大于或等于 2。开始时机器人在其中的 M 位 置上(M 一定是 1~N 中的一个)，机器人可以往左走或者往右走，如果机器人来到 1 位置， 那 么下一步只能往右来到 2 位置;如果机器人来到 N 位置，那么下一步只能往左来到 N-1 位置。 规定机器人必须走 K 步，最终能来到 P 位置(P 也一定是 1~N 中的一个)的方法有多少种。给 定四个参数 N、M、K、P，返回方法数。
法一：递归
public class solution {
public static int ways1(int N, int M, int K, int P) {
// 参数无效直接返回0
if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
return 0;
}
// 总共N个位置，从M点出发，还剩K步，返回最终能达到P的方法数
return walk(N, M, K, P);
}
// N : 位置为1 ~ N，固定参数
// cur : 当前在cur位置，可变参数
// rest : 还剩res步没有走，可变参数
// P : 最终目标位置是P，固定参数
// 该函数的含义：只能在1~N这些位置上移动，当前在cur位置，走完rest步之后，停在P位置的方法数作为返回值返回
public static int walk(int N , int cur , int rest, int P){
// 如果没有剩余步数了，当前的cur位置就是最后的位置
// 如果最后的位置停在P上，那么之前做的移动是有效的
// 如果最后的位置没在P上，那么之前做的移动是无效的
if(rest==0){
return cur==P?1:0;
}
// 如果还有rest步要走，而当前的cur位置在1位置上，那么当前这步只能从1走向2
// 后续的过程就是，来到2位置上，还剩rest-1步要走
if(cur==1){
return walk(N,2,res-1,P);
}
// 如果还有rest步要走，而当前的cur位置在N位置上，那么当前这步只能从N走向N-1
// 后续的过程就是，来到N-1位置上，还剩rest-1步要走
if(cur==N){
return walk(N,N-1,res-1,P);
}
// 如果还有rest步要走，而当前的cur位置在中间位置上，那么当前这步可以走向左，也可以走向右
// 走向左之后，后续的过程就是，来到cur-1位置上，还剩rest-1步要走
// 走向右之后，后续的过程就是，来到cur+1位置上，还剩rest-1步要走
// 走向左、走向右是截然不同的方法，所以总方法数要都算上
return walk(N,cur+1,res-1,P)+walk(N,cur-1,res-1,P);
}
}优化一：递归过程有很多重复的计算，加入二维表作缓存。
f(2,2,)重复计算
public class solution {
public static int ways2(int N, int M, int K, int P) {
int[][] dp =new int [K+1][N+1];
for(int i=0;i<=K;i++){
for(int j=0;j<=N;j++){
dp[i][j]=-1;
}
}
// 参数无效直接返回0
if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
return 0;
}
// 总共N个位置，从M点出发，还剩K步，返回最终能达到P的方法数
return walk(N, M, K, P,dp);
}
public static int walk(int N , int cur , int rest, int P，int[][] dp){
if(dp[rest][cur]!=-1){ //先判断计算的位置是否存在二维表中
return dp[rest][cur];
}
if(rest==0){
dp[rest][cur]=cur==P?1:0;
}
if(cur==1){
dp[rest][cur]=walk(N,2,res-1,P);
}
else if(cur==N){
dp[rest][cur]=walk(N,N-1,res-1,P)
}
else{
dp[rest][cur]=walk(N,cur+1,res-1,P)+walk(N,cur-1,res-1,P)
}
return dp[rest][cur];
}
}优化三：转为动态规划。
其实就是一个建表的过程。
初始赋值：cur无0位置 所以0列无数字。可以初始为-1。
当rest为0时，只有cur在终点位置时为1。
其余点的计算等于
public static int way3(int N, int M, int K, int P) {
int[][] dp =new int [K+1][N+1];
for(int i=1;i<=K;i++){
for(int j=1;j<=N;j++){
if(j==1){ //特殊边界处理
dp[i][j]=dp[i-1][2];
}else if(j==N){
dp[i][j]=dp[i-1][N-1];
}else{
dp[i][j]=dp[i-1][cur+1]+dp[i-1][cur-1];//与左上和右上的值有关
}
}
}
return dp[K][M];
}题目二：换钱的最少货币数
给定数组 arr，arr 中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值 的货币可以使用任意张，再给定一个整数 aim，代表要找的钱数，求组成 aim 的最少货币 数。 首先还是暴力递归求解class solution{
public static int minCoins(int[] arr,int aim){
if(arr=null || aim<0 || arr.length==0){
return -1;
}
return process(arr,0,aim); //每一个index都有拿不拿两种选择
}
// 当前考虑的面值是arr[i]，还剩rest的钱需要找零
// 如果返回-1说明*使用arr[i..N-1]面值的情况下，无论如何也无法找零rest
// 如果返回不是-1，代表*使用arr[i..N-1]面值的情况下，找零rest需要的最少张数
public static int process(int[] arr, int index, int rest){
// 已经没有面值能够考虑了
// 如果此时剩余的钱为0，返回0张
// 如果此时剩余的钱不是0，返回-1
if(res<0){
return -1;
}
if(rest=0)
{
return 0;
}
if(i==arr.length){
return rest==-1;
}
int p1=process(arr,index+1,rest);//不取
int p2=process(arr,index+1,res-arr[index]);//取
if(p1==-1 && p2==-1){
return -1;
}else{
if(p1==-1){
return p1=p2+1;
}
if(p2==-1){
return p1;
}
return Math.min(p1,p2+1);
}
}
}动态规划
public static int minCoins(int[] arr , int aim){
int N =arr.length;
int [][] dp= new int[N+1][aim+1];
//初始表赋值
for(itn row=0;row<=N;row++){
dp[row][0]=0;
}
for(int col=1;col<=aim;col++){
dp[N][col]=-1;
}
for(int index=N-1;index>=0;index--){
for(int rest=1;rest<=aim;rest++){
int p1=dp[index+1][rest];
int p2=-1;
if(rest-arr[index]>=0){
p2=dp[index+1][rest-arr[index]];
}
if(p1==-1 && p2==-1){
dp[index][rest]=-1;
}else{
if(p1==-1){
dp[index][rest]=p2+1;
}
else if(p2==-1){
dp[index][rest]=p1;
}else{
dp[index][rest]=Math.min(p1.p2+1);
}
}
}
return dp[0][aim];
}