B站左程云算法视频笔记06

问题：机器人运动

给一个int N（大于1的正数，表示有N个位置），int S（开始位置），int e（结尾位置），int k（机器人必须走K步）

机器人可以往左走往右走，1位置只能往右，N位置只能往左，

S到e，必须走K步，问有几种方法？

例：N = 5， S= 2， e = 4 ， k = 4

23454、23434、23234、21234四种方法

public static int walkWays(int N, int E, int S, int K){
    return f(N, E, K, S);
}

//一共是1~N这么多位置  固定参数
//最终目标是E  固定参数
//当前在cur位置 
//还剩rest步需要走
//返回方法数
public static int f(int N, int E, int rest, int cur){
    if( rest == 0){
        return cur == E ? 1 : 0;
    }//base case
    //rest > 0 还有路可以走
    if( cur == 1){ // 1 - > 2
        return f(N, E, rest - 1, 2);
    }
    if( cur == N){ // N -> N -1
        return f(N, E, rest - 1, N - 1);
    }
    //中间位置
    return f(N, E, rest - 1, cur - 1) + f(N, E, rest - 1, cur + 1);
}

N E是固定参数，rest 和cur是可变参数

可变参数固定，返回值一样，无后效性

存在重复的过程

加缓存，空间换时间

try（暴力递归）-> 记忆化搜索

public static int walkWays2(int N, int E, int S, 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 f2(N, E, K, S,dp);

}

public static int f2(int N, int E, int rest, int cur,int[][] dp){
    if(dp[rest][cur] != -1){
        return dp[rest][cur];
    }    
    //缓存没命中
    if( rest == 0){
        dp[rest][cur] == cur == E ? 1: 0; 
        return cur == E ? 1 : 0;
    }//base case
    
    //rest > 0 还有路可以走
    if( cur == 1){ // 1 - > 2
        dp[rest][cur] =f2(N, E, rest - 1, 2);
    }
    else if( cur == N){ // N -> N -1
        dp[rest][cur] = f2(N, E, rest - 1, N - 1);
    }else {
    //中间位置
        dp[rest][cur] =f(N, E, rest - 1, cur - 1) + f(N, E, rest - 1, cur + 1);
    }
    return dp[rest][cur];
}

O(k*n)

整理位置依赖

假设有5个位置

边界位置依赖

 普遍位置依赖左上角和右上角的值

汇总

以上即严格表结构的动态规划（纠结位置依赖的顺序）

给一个正数数组，每一个值代表一枚硬币，给一个aim，怎么最少的硬币给出aim

//保证arr中都是正数
public static int minCoins1(int[] arr, int aim){
    return f(arr, 0, aim);
}

//arr硬币都在其中，固定参数
//aim：最终要达成的目标，固定参数
//arr[index...]组成rest这么多钱，最少的硬币数量返回
public static int process(int[] arr, int index, int rest){
    if(rest < 0){
        return -1;
    }
    if(rest == 0){
        return 0;
    }
    // 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 && p2Next == -1){
        return -1;
    }else{
        if(p1 == -1){
            return p2Next + 1;
        }
        if(p2Next == -1){
            return p1;
        }
        return Math.min(p1,p2Next+1);
    }
}

 改成记忆化搜索的方式

public static int minCoins(int[] arr, int aim){
    int[][] dp = new int[arr.length+1][aim+1];
    for(int i = 0; i <= arr.length; i++){
        for(int j = 0; j <= aim; j++){
            dp[i][j] = -2;
        }
    }
    return process2(arr, 0, aim, dp);
}

public static int process2(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 = process2(arr, index + 1, rest, dp);
        int p2Next = process2(arr, index + 1, rest - arr[index], dp);
        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[index][rest];
}

严格表结构

public static int minCoins3(int[] arr, int aim){
    int N = arr.length;
    int[][] dp = new int[arr.lrnght + 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 row = N - 1; index >= 0; index--){
        for(int rest = 1; rest <= aim; rest++){
            int p1 = dp[index+1][rest];
            int p2Next = -1;
            if(rest - arr[index] >= 0){
                p2Next = dp[index + 1][rest - arr[index]];
            }//考虑越界
        if(p1 == -1 && p2Next == -1){
            dp[index][rest] = -1;
        }else{
        if(p1 == -1){
            dp[index][rest] = p2Next + 1;
        }
        if(p2Next == -1){
            dp[index][rest] = p1;
        }
           dp[index][rest] = Math.min(p1,p2Next+1);
        }
        }
    }
    return dp[0][aim];
}

严格表结构：1.分析可变参数的变化范围 2.标出要计算的终止位置 3.表出不用计算直接出答案的位置 base case 4. 推出普遍位置如何依赖其他位置（看依赖） 5.确定依次计算的顺序，定出严格表是从那些格子到哪些格子