动态规划基础入门【1】

╰+哭是因爲堅強的太久メ 2024-04-07 12:50 88阅读 0赞

## 动态规划基础入门 ##

### 1 基础概念 ###

### 2 经典题目 ###

> 诀窍：常规递归 -> 缓存表 -> 动态规划  
> 需要有一个尝试的过程

#### 2.1 机器人走的方法数 ####

假设有排成一行的N个位置，记为1~N，N>=2  
开始时，机器人在其中的M位置上（M一定是1~N中的一个）  
如果机器人来到1位置，那么下一步只能往右来到2位置；  
如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；  
如果机器人来到中间位置，那么下一步可以往左走或者往右走；  
规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种  
给定四个参数 N、M、K、P，返回方法数。

##### 2.1.1 基础写法（普通递归） #####

> 普通递归方式，但是会有太多重复值计算；类比斐波那契,f(6) = f(5) + f(4), f(5) = f(4) + f(3)

/**
     * 普通递归方式【缺点：有太多重复值计算】
     */
    public class RobotWalkDemo {
        
    
        /**
         * @param N     一共有多少个位置
         * @param start 机器人起始位置
         * @param aim   机器人目标位置
         * @param K     一共可以走几步
         * @return
         */
        public static int ways1(int N, int start, int aim, int K) {
        
            if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
        
                return -1;
            }
            return process1(start, K, aim, N);
        }
    
        /**
         * @param cur  机器人当前位置
         * @param rest 剩余步数
         * @param aim  目标位置
         * @param N    一共有多少位置【1~N】
         * @return 机器人从cur出发，走过rest步之后，最终停在aim的方法数，是多少？
         */
        public static int process1(int cur, int rest, int aim, int N) {
        
            if (rest == 0) {
        
                //没有步数了，看看是否走到了目标位置
                return cur == aim ? 1 : 0;
            }
            //机器人在1位置，只能往右走
            if (cur == 1) {
        
                return process1(cur + 1, rest - 1, aim, N);
            }
            //机器人在最后位置N，只能往左走
            if (cur == N) {
        
                return process1(cur - 1, rest - 1, aim, N);
            }
            //机器人在中间，可以往两边走，结果为左右数之和
            return process1(cur - 1, rest - 1, aim, N) + process1(cur + 1, rest - 1, aim, N);
        }
        
        public static void main(String[] args) {
        
            System.out.println(ways1(5, 2, 4, 6));
        }
    }

##### 2.1.2 使用缓存表 #####

> 将每次结果都放在一个dp缓存表中，如果缓存中有数据直接从缓存表拿

/**
     * 利用缓存表【记忆化搜索】
     *
     * @param N
     * @param start
     * @param aim
     * @param K
     * @return
     */
    public static int ways2(int N, int start, int aim, int K) {
        
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
        
            return -1;
        }
        //利用缓存表【dp】:K+1是因为0步也算一种情况
        int[][] dp = new int[N + 1][K + 1];
        for (int i = 0; i <= N; i++) {
        
            for (int j = 0; j <= K; j++) {
        
                dp[i][j] = -1;
            }
        }
        //dp就是缓存表
        //dp[cur][rest] == -1 -> process2(cur, rest) 之前没算过
        //dp[cur][rest] != -1 -> process2(cur, rest) 之前算过
        return process2(start, K, aim, N, dp);
    }
    
    //cur范围：1~N
    //rest范围：0~K
    public static int process2(int cur, int rest, int aim, int N, int[][] dp) {
        
        if (dp[cur][rest] != -1) {
        
            //缓存表中有值，直接取
            return dp[cur][rest];
        }
        //之前没有算过
        int ans = 0;
        if (rest == 0) {
        
            ans = cur == aim ? 1 : 0;
        } else if (cur == 1) {
        
            ans = process2(cur + 1, rest - 1, aim, N, dp);
        } else if (cur == N) {
        
            ans = process2(cur - 1, rest - 1, aim, N, dp);
        } else {
        
            ans = process2(cur - 1, rest - 1, aim, N, dp) + process2(cur + 1, rest - 1, aim, N, dp);
        }
        dp[cur][rest] = ans;
        return ans;
    }

##### 2.1.3 动态规划 #####

/**
      * 利用标准动态规划求解
      *
      * @param N     位置个数
      * @param start 起始位置
      * @param aim   目标位置
      * @param K     步数
      * @return
      */
     public static int ways3(int N, int start, int aim, int K) {
        
         if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
        
             return -1;
         }
         int[][] dp = new int[N + 1][K + 1];
         //base case
         dp[aim][0] = 1;
         for (int rest = 1; rest <= K; rest++) {
        
             //当cur为第一个位置时候
             dp[1][rest] = dp[2][rest - 1];
             for (int cur = 2; cur < N; cur++) {
        
                 //cur为中间位置
                 dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
             }
             //当cur为最后一个位置时
             dp[N][rest] = dp[N - 1][rest - 1];
         }
         return dp[start][K];
     }

#### 2.2 先手后手纸牌游戏 ####

给定一个整型数组arr，代表数值不同的纸牌排成一条线  
玩家A和玩家B依次拿走每张纸牌  
规定玩家A先拿（先手）， 玩家B后拿（后手）  
但是每个玩家每次只能拿走最左或最右的纸牌  
玩家A和玩家B都绝顶聪明【会考虑下一次让对方拿到最小的】  
请返回最后获胜者的分数。

##### 2.2.1 常规递归求解 #####

> 按照常规思路尝试即可

/**
     * 常规递归方法求解
     */
    public class CardsInLine {
        
    
        public static int win1(int[] arr) {
        
            if (arr == null || arr.length == 0) {
        
                return 0;
            }
            //先手获得的分数
            int first = f1(arr, 0, arr.length - 1);
            //后手获得的分数
            int second = g1(arr, 0, arr.length - 1);
            return Math.max(first, second);
        }
    
        //先手
        public static int f1(int[] arr, int L, int R) {
        
            if (L == R) {
        
                //只剩一张牌了，先手直接拿到
                return arr[0];
            }
            //第一种情况：先手拿左手边的牌【左手牌的值+下一次自己作为后手时拿的值】
            int p1 = arr[L] + g1(arr, L + 1, R);
            //第二种情况：先拿右手边的牌【右手边的牌+下一次作为后手时拿的最大值】
            int p2 = arr[R] + g1(arr, L, R - 1);
            //我肯定选择获得分数最大的走法
            return Math.max(p1, p2);
        }
    
        //后手
        public static int g1(int[] arr, int L, int R) {
        
            if (L == R) {
        
                //只剩一张牌了，牌肯定被先手拿走
                return 0;
            }
            //第一种情况：对手拿的左手边的值
            int p1 = f1(arr, L + 1, R);
            //第二种情况：对手拿的自己右手边的值
            int p2 = f1(arr, L, R - 1);
            //我作为第一局的后手，肯定只有获得两种情况的最小值【对手会想尽办法让我获得最小值】
            return Math.min(p1, p2);
        }
    
        public static void main(String[] args) {
        
            int[] arr = {
         5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7 };
            System.out.println(win1(arr));
        }
    
    }

##### 2.2.2 缓存表方式 #####

> 两张缓存表fmap、gmap，fmap\[L\]\[R\]其值代表当数组的左边界为L时，右边界为R时的值

/**
     * 使用缓存表【两张】
     * @param arr
     * @return
     */
    public static int win2(int[] arr){
        
        if(arr == null || arr.length == 0){
        
            return 0;
        }
        int N = arr.length;
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        for(int i = 0; i < N; i++){
        
            for(int j = 0; j < N; j++){
        
                fmap[i][j] = -1;
                gmap[i][j] = -1;
            }
        }
        int first = f2(arr, 0, arr.length - 1, fmap, gmap);
        int second = g2(arr, 0, arr.length - 1, fmap, gmap);
        return Math.max(first, second);
    }
    
    public static int f2(int[] arr, int L, int R, int[][] fmap, int[][] gmap){
        
        if(fmap[L][R] != -1){
        
            return fmap[L][R];
        }
        int ans = 0;
        if(L == R){
        
            //先手直接获得
            ans = arr[L];
        } else {
        
            //情况一：拿的左边的牌
            int p1 = arr[L] + g2(arr, L + 1, R, fmap, gmap);
            //情况二：拿的右边的牌
            int p2 = arr[R] + g2(arr, L, R - 1, fmap, gmap);
            ans = Math.max(p1, p2);
        }
        fmap[L][R] = ans;
        return ans;
    }
    
    public static int g2(int[] arr, int L, int R, int[][] fmap, int[][] gmap){
        
        if(gmap[L][R] != -1){
        
            return gmap[L][R];
        }
        int ans = 0;
        if(L != R){
        
            //情况一：对手拿走了左边的牌
            int p1 = f2(arr, L+1, R, fmap, gmap);
            //情况二：对手拿走了右边的牌
            int p2 = f2(arr, L, R - 1, fmap, gmap);
            ans = Math.min(p1, p2);
        }
        gmap[L][R] = ans;
        return ans;
    }

##### 2.2.3 动态规划 #####

/**
     * 动态规划求解
     * @param arr
     * @return
     */
    public static int win3(int[] arr) {
        
        if (arr == null || arr.length == 0) {
        
            return 0;
        }
        int N = arr.length;
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        for (int i = 0; i < N; i++) {
        
            //L == R 情况
            fmap[i][i] = arr[i];
        }
        for (int startCol = 1; startCol < N; startCol++) {
        
            int L = 0;//row
            int R = startCol;//col
            //行不会越界，是列提前越界
            while (R < N) {
        
                //先手
                fmap[L][R] = Math.max(arr[L] + gmap[L + 1][R], arr[R] + gmap[L][R - 1]);
                //后手
                gmap[L][R] = Math.min(fmap[L + 1][R], fmap[L][R - 1]);
                L++;
                R++;
            }
        }
        return Math.max(fmap[0][N - 1], gmap[0][N - 1]);
    }

#### 2.3 包中最大价值（背包问题） ####

给定两个长度都为N的数组weights和values，weights\[i\]和values\[i\]分别代表 i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少?

动态规划解法：由尝试 -> 动态规划

##### 2.3.1 尝试 #####

//背包问题：返回包得到的最大价值
    public class KnapsackDemo {
        
    
        /**
         * 假设w、v数组中没有负数
         *
         * @param w   物品重量
         * @param v   物品对应价值
         * @param bag 包的容量
         * @return
         */
        public static int maxValue(int[] w, int[] v, int bag) {
        
            if (w == null || v == null || w.length != v.length || w.length == 0) {
        
                    return 0;
            }
            //尝试函数
            return process(w, v, 0, bag);
        }
    
        //index 0 ~ N
        //rest 负数 ~ bag【包的剩余容量】
        public static int process(int[] w, int[] v, int index, int rest){
        
            if(rest < 0){
        
                //rest小于零，表明之前的尝试是错误的
                return -1;
            }
            if(index == w.length){
        
                return 0;
            }
            //没有要index位置的货物
            int p1 = process(w, v, index + 1, rest);
            int p2 = 0;
            int next = process(w, v, index + 1, rest - w[index]);
            if(next != -1){
        
                //该尝试可行
                //要了index位置的货物
                p2 = v[index] + next;
            }
            return Math.max(p1, p2);
        }
    
    
        public static void main(String[] args) {
        
            int[] weights = {
         3, 2, 4, 7, 3, 1, 7 };
            int[] values = {
         5, 6, 3, 19, 12, 4, 2 };
            int bag = 15;
            System.out.println(maxValue(weights, values, bag));//42
    //        System.out.println(dp(weights, values, bag));
        }
    }

##### 2.3.2 dp方法 #####

由尝试改为动态规划：递归改为从数组中拿值

/**
      * 动态规划实现
      * @param w
      * @param v
      * @param bag
      * @return
      */
     public static int dp(int[] w, int[] v, int bag){
        
         //条件判断不变【照抄"尝试"】
         if(w == null || v == null || w.length != v.length || w.length == 0){
        
             return 0;
         }
         int N = w.length;
         int[][] dp = new int[N+1][bag+1];
         for(int index = N - 1; index >= 0; index--){
        
             //依赖index+1位置，由下往上推
             for(int rest = 0; rest <= bag; rest++){
        
                 //process(w, v, index + 1, rest);
                 //process(w, v, index + 1, rest - w[index]);
                 //同一行的数据相互是不依赖的，因此可以从左往右填，也可以从右往左填
                 int p1 = dp[index+1][rest];
                 int p2 = 0;
                 int next = rest - w[index] < 0 ? -1 : dp[index+1][rest - w[index]];
                 if(next != -1){
        
                     p2 = v[index] + next;
                 }
                 dp[index][rest] = Math.max(p1, p2);
             }
         }
         return dp[0][bag];
     }

#### 2.4 数字-字符串转换 ####

规定1和A对应、2和B对应、3和C对应…26和Z对应，那么一个数字字符串比如"111”就可以转化为:“AAA”、“KA"和"AK”，给定一个只有数字字符组成的字符串str，返回有多少种转化结果

##### 2.4.1 尝试 #####

//数字转字符串【转法】
    //str只含数字0~9
    public static int number(String str) {
        
        if (str == null || str.length() == 0) {
        
            return 0;
        }
        return process(str.toCharArray(), 0);
    }
    
    //str[0..i-1]转化无需过问
    //str[i...]去转化，返回有多少种转化方案
    public static int process(char[] str, int i) {
        
        if (i == str.length) {
        
            return 1;
        }
        //i没走到最后，说明还有数字剩余
        if (str[i] == '0') {
        
            //之前的决定有问题[1~26：没有单独的0]
            return 0;
        }
        //str[i] != '0'
        //可能性1：单转
        int ways = process(str, i + 1);
        //可能性2：合并转【11 -> K】
        if (i + 1 < str.length && (str[i] - '0') * 10 + str[i + 1] - '0' < 27) {
        
            ways += process(str, i + 2);
        }
        return ways;
    }

##### 2.4.1 递归（一维数组） #####

//从右往左的动态规划
    //dp[i]:str[i..]有多少种转化方式
    public static int dp1(String s){
        
       if(s == null || s.length() == 0){
        
           return 0;
       }
       char[] str = s.toCharArray();
       int N = str.length;
       int[] dp = new int[N+1];
       dp[N] = 1;
       for(int i = N - 1; i >= 0; i--){
        
           if(str[i] != '0'){
        
               int ways = dp[i+1];
               if(i + 1 < str.length && (str[i] - '0') * 10 + str[i+1] - '0' < 27){
        
                   ways += dp[i+2];
               }
               dp[i] = ways;
           }
       }
       return dp[0];
    }

#### 2.5 贴纸拼接字符串(LeetCode - 691. 贴纸拼词) ####

给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文，arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来，返回需要至少多少张贴纸可以完成这个任务。  
例子：str= “babac”，arr = \{“ba”,“c”,“abcd”\}

> ba + ba + c 3  
> abcd + abcd 2 abcd+ba 2

所以返回2(最少)

##### 2.5.1 尝试 #####

//返回最少所用贴纸数
    public static int minStickers(String[] stickers, String target) {
        
        int ans = process1(stickers, target);
        //如果返回最大值，表明没有结果
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
    
    /**
     * @param stickers 贴纸数组
     * @param target   目标字符串
     * @return 最少张数
     */
    public static int process1(String[] stickers, String target) {
        
        if (target.length() == 0) {
        
            return 0;
        }
        int min = Integer.MAX_VALUE;
        //每一张作为第一张尝试
        for (String first : stickers) {
        
            //first能够消除掉多少target里面的字符
            String rest = minus(target, first);
            if (rest.length() != target.length()) {
        
                min = Math.min(min, process1(stickers, rest));
            }
        }
        //如果min不是最大值表明有效【+1加上本身】
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }
    
    public static String minus(String s1, String s2) {
        
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int[] count = new int[26];
        for (char cha : str1) {
        
            count[cha - 'a']++;
        }
        for (char cha : str2) {
        
            count[cha - 'a']--;
        }
        StringBuilder stb = new StringBuilder();
        for (int i = 0; i < 26; i++) {
        
            if (count[i] > 0) {
        
                for (int j = 0; j < count[i]; j++) {
        
                    stb.append((char) (i + 'a'));
                }
            }
        }
        return stb.toString();
    }

##### 2.5.2 减枝+贪心 #####

//减枝
    public static int minStickers2(String[] stickers, String target){
        
        int N = stickers.length;
        //关键优化（用词频表替代贴纸数组）
        int[][] counts = new int[N][26];
        for(int i = 0; i < N; i++){
        
            char[] str = stickers[i].toCharArray();
            for(char cha : str){
        
                counts[i][cha - 'a']++;
            }
        }
        int ans = process2(counts, target);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
    
    /**
     *
     * @param stickers 贴纸词频数组
     * @param t 目标字符串
     * @return
     */
    public static int process2(int[][] stickers, String t){
        
        if(t.length() == 0){
        
            return 0;
        }
        //target做出词频统计
        char[] target = t.toCharArray();
        int[] tcounts = new int[26];
        for(char cha : target){
        
            tcounts[cha - 'a']++;
        }
        int N = stickers.length;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < N; i++){
        
            //尝试第一张贴纸是谁
            int[] sticker = stickers[i];
            //最关键的优化（最重要的剪枝，这一步也是贪心）
            if(sticker[target[0] - 'a'] > 0){
        
                StringBuilder stb = new StringBuilder();
                for(int j = 0; j < 26; j++){
        
                    if(tcounts[j] > 0){
        
                        int nums = tcounts[j] - sticker[j];
                        for(int k = 0; k < nums; k++){
        
                            stb.append((char)(j+'a'));
                        }
                    }
                }
                String rest = stb.toString();
                min = Math.min(min, process2(stickers, rest));
            }
        }
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }

##### 2.5.3 dp（缓存表） #####

//方法三：加缓存表【dp，记忆化搜索】
    public static int minStickers3(String[] stickers, String target){
        
        int N = stickers.length;
        int[][] counts = new int[N][26];
        for(int i = 0; i < N; i++){
        
            char[] str = stickers[i].toCharArray();
            for(char cha : str){
        
                counts[i][cha - 'a']++;
            }
        }
        HashMap<String, Integer> dp = new HashMap<>();
        dp.put("", 0);
        int ans = process3(counts, target, dp);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
    
    public static int process3(int[][] stickers, String t, HashMap<String, Integer> dp){
        
        if(dp.containsKey(t)){
        
            return dp.get(t);
        }
        char[] target = t.toCharArray();
        int[] tcounts = new int[26];
        for(char cha : target){
        
            tcounts[cha - 'a']++;
        }
        int N = stickers.length;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < N; i++){
        
            int[] sticker = stickers[i];
            if(sticker[target[0] - 'a'] > 0){
        
                StringBuilder stb = new StringBuilder();
                for(int j = 0; j < 26; j++){
        
                    if(tcounts[j] > 0){
        
                        int nums = tcounts[j] - sticker[j];
                        for(int k = 0; k < nums; k++){
        
                            stb.append((char) (j+'a'));
                        }
                    }
                }
                String rest = stb.toString();
                min = Math.min(min, process3(stickers, rest, dp));
            }
        }
        int ans = min + (min == Integer.MAX_VALUE ? 0 : 1);
        dp.put(t, ans);
        return ans;
    }