一、暴力递归到动态规划

try （暴力递归）

        |

        |

记忆化搜索（加入记忆数组）

        |

        |

严格表结构（dp）

【从起点到到终点的走法】

        给定一个参数N，代表N个位置，N>1；给定一个参数M，表示开始的位置，1<=M<=N；给定一个参数P，表示结束的位置，1<=P<=N；给定一个参数K，表示机器人必须走K步从S到E。

走的规则：随意往左或者往右，来到1位置，只能往2走；来到N位置，只能往N-1走

求：M -> P，必须走K步，有多少种方法？ 

        1、暴力递归

public static int walkWay1(int N, int P, int M, int K){
    return process(N, P, K, M);   
}

public static int process(int N, int E, int rest, int cur){
    if(rest==0){                                    //basecase
        return cur==E?1:0;
    }
    if(cur==1){                                     
        res += process(N, E, rest-1, cur+1);
    }
    if(cur==N){
        res += process(N, E, rest-1, cur-1);
    }
    return process(N, E, rest-1, cur-1) + process(N, E, rest-1, cur+1);
}

        2、记忆化搜索

        如：p(3, 1) -> p(2, 2)          p(3, 3) -> p(2, 2) + p(2, 4)

        p(3, 1) 和 p(3, 3)都能走到p(2, 2)，因此对于p(2, 2)来说，无论之前的路如何选择，走到这一步，p(2, 2)的结构都一样，因此，可以构建一个类似“缓存”的结构来记录

        这样每个格子只计算一遍，总格子大小为O(K*N)，访问临近格子的时间复杂度为O(1)

public static int walkWays2(int N, int P, int M, int K){
    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;
        }
    }
    return process2(N, P, K, M, dp);
}

public static int process2(int N, int E, int rest, int cur, int[][] dp){
    if(dp[rest][cur]!=-1){                    // basecase
        return dp[rest][cur];
    }
    if(rest==0){                              // basecase
        dp[rest][cur] = cur==E?1:0;
        return dp[rest][cur];
    }
    if(cur==1){
        dp[rest][cur] = process(N, E, rest-1, cur+1, dp);
    }else if(cur==N){
        dp[rest][cur] = process(N, E, rest-1, cur-1, dp);
    }else {
        dp[rest][cur] = process(N, E, rest-1, cur-1, dp) + process(N, E, rest-1, cur+1, dp);
    }
    return dp[rest][cur];
}

        3、动态规划

假设N=5，K=3，E=4，有

        1）根据base case，K=0的时候，N为4时为1，其余全为0

        2）查看边界情况，N为1的时候，依赖(K-1, N+1)的位置；N为5的时候，依赖(K-1, N-1)的位置；N只考虑1-5的情况，不考虑0

        3）查看递归中中间值的依赖，依赖的是(K-1, N+1)和(K-1, N-1)的和

  N 0 1 2 3 4 5
K  -------------  
0   X 0 0 0 1 0
1   X 0 0 1 0 1
2   X 0 1 0 2 0
3   X 1 0 3 0 2
4   X 0 4 0 5 0

public static int walkWays3(int N, int P, int M, int K){
    int[][] dp = new int[K+1][N+1];
    dp[0][P] = 1;              // base case  
    for(int rest = 1; rest<=K; rest++){
        for(int cur=1; cur<=N; cur++){
            if(cur==1){
                dp[rest][cur] = dp[rest-1][cur+1];        // 边界条件
            } else if(cur==N){
                dp[rest][cur] = dp[rest-1][cur-1];        // 边界条件
            } else {
                dp[rest][cur] = dp[rest-1][cur+1] + dp[rest-1][cur-1];        // 中间值
            }
        }    
    }
    return dp[K][M];            //目标是K，M
}        

【硬币组成方式】

        给定一个正数数组，每个数代表一枚硬币的面值，给一个值10，最少是多少枚硬币能组成该值？

        1、暴力递归：

public static int minCoins1(int[] arr, int aim){
    int num = process(arr, 0, aim);
    return num==-1?-1: num;
}

// arr[index....]组成rest这么多钱，最少的硬币数量返回
public static int process(int[] arr, int index, int rest){
    //rest < 0
    if(rest < 0){
        return -1;
    } 
    
    // rest == 0
    if(rest==0){
        return 1;
    }

    // rest > 0，但没硬币
    if(index==arr.length){
        return -1;
    }

    // rest > 0,还有硬币
    int p1 = process(arr, index+1, rest);
    int p2Next = process(arr, index+1, rest-arr[index]);
    
    if(p1==-1 && p2==-1){
        return -1;
    } else {
        if(p1==-1){                    //选1是错误的
            return 1 + p2Next;
        }else if(p2==-1){                //选2是错误的
            return p1;        
        }else {
            return Math.min(p1, 1+p2Next);
        }
    }        
}

        

        2、记忆化搜索

public static int min2(int[] arr, int aim){
    int N = arr.length;
    int[][] dp = new int[N+1][aim+1];
    for(int i = 0; i<=N; i++){
        for(int j = 0; j<=aim; j++){
            dp[i][j] = -2;
        }
    }
    int num = f2(arr, 0, aim dp);
}

public static int f2(int[] arr, int index, int rest, int[][] dp){
    if(rest < 0){
        return -1;
    }

    if(dp[index][rest]!=-2){
        return dp[index][rest];
    }
    
    if(rest==0){
        dp[index][rest] = 0;
    }else if(index==arr.length){
        dp[index][rest] = -1;
    }else{

        int p1 = f2(arr, index+1, rest);
        int p2Next = f2(arr, index+1, rest-arr[index]);

        if(p1==-1&&p2Next==-1){
            dp[index][rest] = -1;
        } else{
            if(p1==-1){
                dp[index][rest] = 1+p2Next;
            }else if(p2==-1){
                dp[index][rest] = p1;
            }else {
                dp[index][rest] = Math.min(1+p2Next, p1);
            }
        }
    }
    return dp[index][rest];
}

        3、动态规划

假设arr [2, 3, 5, 7, 2],  aim = 10

        rest  0  1  2  3  4  5  6  7  8  9  10 
---------------------------------------------------
index     0   0                              T
          1   0
          2   0
          3   0
          4   0
          5   0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

1）确定base case：
    rest = 0 的时候，为0
    index == 终止位置，为-1
2) 普遍位置：
    主函数都会调用 index+1，rest的值，以及index+1,rest-arr[index]的值
3) 目标值：
    T(0, aim)，表示从0出发，最少多少枚硬币能组成aim的面值

public static int min3(int[] arr, int aim){
    int N = arr.length;
    int[][] dp = new int[N+1][aim+1];

    for(int 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 p2Next = rest-arr[index]>=0?dp[index+1][rest-arr[index]]:-1;
            if(p1 == -1 && p2Next == -1){
                dp[index][rest] = -1;
            } else {
                if(p1==-1){
                    dp[index][rest] = p2Next+1;
                } else if(p2Next==-1){
                    dp[index][rest] = p1;
                } else{
                    dp[index][rest] = Math.min(p1, p2Next+1);
                }
            }
        }
    }
    return dp[0][aim];
}

二、暴力递归改动态规划总结

暴力递归——>记忆化搜索——>严格表缓存

1、确定可变参数范围

2、标记出终止位置

3、标出不用计算就能得到的答案（根据base case）

4、推普遍位置如何依赖其他位置

5、确定依次计算的顺序

【象棋马跳问题】

        给定一个象棋棋盘，x~[0，.....，8]，y~[0，......，9]，马从(0, 0)出发，到(x, y)的位置必须要跳k步，求一共有多少种方式。

        1、暴力递归，将问题转化为从(x, y)跳到(0, 0)有多少种方法

public static int getWays(int x, int y, int k){
    return process(x, y, k);
}

public static int process(int x, int y, int step){
    if(x<0 || x>8 || y<0 || y>9){        // 越界
        return 0;
    }
    if(step==0){
        return (x==0 && y==0)? 1: 0;
    }
    return process(x-2, y-1, step-1)+
           process(x+2, y-1, step-1)+
           process(x-2, y+1, step-1)+
           process(x+2, y+1, step-1)+
           process(x-1, y-2, step-1)+
           process(x+1, y-2, step-1)+
           process(x-1, y+2, step-1)+
           process(x+1, y+2, step-1);
}

        2、动态规划

public static int dpWay(int x, int y, int k){

    int[][][] dp = new int[9][10][k+1];
    dp[0][0][0] = 1;
    for(int h=1; h<=k; h++){
        for(int r=0; r<=8; r++){
            for(int c=0; c<=9; c++){
                dp[r][c][h] += getValues(dp, r-1, c-2, h-1);
                dp[r][c][h] += getValues(dp, r+1, c-2, h-1);
                dp[r][c][h] += getValues(dp, r-1, c+2, h-1);
                dp[r][c][h] += getValues(dp, r+1, c+2, h-1);
                dp[r][c][h] += getValues(dp, r-2, c-1, h-1);
                dp[r][c][h] += getValues(dp, r+2, c-1, h-1);
                dp[r][c][h] += getValues(dp, r-2, c+1, h-1);
                dp[r][c][h] += getValues(dp, r+2, c+1, h-1);
            }
        }
    }
    return dp[x][y][k];
}

public static int getValues(int[][][] dp, x, y, step){
    if(x<0 || x>8 || y<0 || y>9){
        return 0;
    }
    return dp(x, y, step);
}

三、斜率优化

        通过观察，若存在枚举行为，可以通过某种方式省掉

【找零问题】

        给定一个正数数组，里面的数字不重复，每一个数字代表铅笔的面值，给定数X，在同一种纸币能使用任意张的情况下，完成X的找零有多少种方法？

        1、暴力递归

public static int way1(int[] arr, int aim){
    return process(arr, 0, aim);
}


// 可以自由使用arr[index...]所有的货币
// 需要搞定的钱数是rest
// 返回找零的方法
public static int process(int[] arr, int index, int rest){
    if(index==arr.length){
        return rest==0?1: 0;
    }
    int ways = 0;

    // arr[index] 0张 1张 ... 不要超过rest的张数
    for(int zhang=0; arr[index]*zhang<=rest; zhang++){
        ways += process(arr, index+1, rest-arr[index]*zhang);
    }
    return ways;
}

        2、动态规划

假设arr[3, 5, 1, 2]，aim=10   

   aim 0 1 2 3 4 5 6 7 8 9 10
index ------------------------
  0                         T
  1
  2                ？
  3               
  4    1 0 0 0 0 0 0 0 0 0 0

1) 目标值：（0, 10)
2) base case：
    index==n：rest==0的时候是1；rest其余时候是0
3) 普遍位置依赖：
        假设这会要处理的位置是(2, 6),arr[index]=1
        zhang=0时，依赖(index+1, rest) = (3, 6)
        zhang=1时，依赖(index+1, rest-arr[index]) = (3, 5)
        zhang=2时，依赖(index+1, rest-2*arr[index]) = (3, 4)
    .......
        zhang=6时，依赖(index+1, rest-6*arr[index]) = (3, 0)
   加起来        

public static int dpWay(int[] arr, int aim){
    int N = arr.length;
    int[][] dp = new int[N+1][aim+1];
    dp[N][0] = 1;
    for(int index=N-1; index>=0; index--){
        for(int rest=0; rest<=aim; rest++){
            int ways = 0;
            for(int zhang=0; arr[i]*zhang<=rest;zhang++){
                ways += dp[index+1][rest-arr[index]*zhang];
            }
            dp[index][rest] = ways;
        }
    }
    return dp[0][aim];
}

        3、斜率优化

        通过进一步观察，可以发现

   aim 0 1 2 3 4 5 6 7 8 9 10
index ------------------------
  0                         T
  1
  2            x   ？
  3   ...  c   b   a  
  4    1 0 0 0 0 0 0 0 0 0 0

？位置的值取决于a、b、c、.....，x位置的值取决于b、c、.....

因此，求？位置的值可以简化为 x + a

public static int dpWay(int[] arr, int aim){
    int N = arr.length;
    int[][] dp = new int[N+1][aim+1];
    dp[N][0] = 1;
    for(int index=N-1; index>=0; index--){
        for(int rest=0; rest<=aim; rest++){
            dp[index][rest] = dp[index+1][rest];
            if(rest-arr[index]>0){
                dp[index][rest] += dp[index][rest-arr[index]];
            }
        }
    }
    return dp[0][aim];
}