动态规划练习

1.0-1 背包问题

选择几件物品,装载到背包中。在不超过背包所能装载重量的前提下,如何让背包中物品的总重量最大?

(1)回溯解法

时间复杂度O(2^n)

    private int maxW = Integer.MIN_VALUE; // 结果放到maxW中
    /**
     * 
     * @param items 每个物品的重量
     * @param n 物品个数
     * @param i 考察到哪个物品
     * @param cw 当前已经装进去的物品的重量和
     * @param lw 背包重量
     */
    public void f(int[] items, int n, int i, int cw, int lw) {
        if (i == n || cw == lw) {// cw==w表示装满了;i==n表示已经考察完所有的物品
            if (cw > maxW) {
                maxW = cw;
            }
            return;
        }
        f(items, n, i + 1, cw, lw);//不装
        if (cw + items[i] <= lw) {
            f(items, n, i + 1, cw + items[i], lw);//装进背包
        }
    }

(2)备忘录解法

    private int maxW = Integer.MIN_VALUE; // 结果放到maxW中
    private int[] weight = {2, 2, 4, 6, 3};  // 物品重量
    private int n = 5; // 物品个数
    private int w = 9; // 背包承受的最大重量
    private boolean[][] mem = new boolean[n][w + 1];//重量可以等于w

    public void f(int i, int cw) {
        if (cw == w || i == n) {
            if (cw > maxW) {
                maxW = cw;
            }
            return;
        }
        if (mem[i][cw]) return;
        mem[i][cw] = true;
        f(i + 1, cw);
        if (cw + weight[i] <= w) {
            f(i + 1, cw + weight[i]);
        }
    }

(3)动态规划解法

时间复杂度: O(n*w)

    public void kmpF(int[] weight, int n, int w) {
        boolean[][] state = new boolean[n][w + 1];
        state[0][0] = true;
        if (weight[0] <= w) {
            state[0][weight[0]] = true;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= w; j++) {
                if (state[i - 1][j]) {
                    state[i][j] = true;
                }
            }
            for (int j = 0; j <= w - weight[i]; j++) {
                if (state[i - 1][j]) {
                    state[i][j + weight[i]] = true;
                }
            }
        }
        for (int i = w; i >= 0; i--) {
            if (state[n - 1][i]) {
                System.out.println("最大重量为:" + i);
                break;
            }
        }
    }

使用一维数组降低空间消耗:

 public static void kmpF2(int[] weight, int n, int w) {
        boolean[] state = new boolean[w + 1];
        state[0] = true;
        if (weight[0] <= w) {
            state[weight[0]] = true;
        }
        for (int i = 1; i < n; i++) {
            for (int j = w - weight[i]; j >= 0; j--) {//j 需要从大到小来处理。如果我们按照 j 从小到大处理的话,会出现 for 循环重复计算的问题。
                if (state[j]) {
                    state[j + weight[i]] = true;
                }
            }
        }
        for (int i = w; i >= 0; i--) {
            if (state[i]) {
                System.out.println("最大重量为:" + i);
                break;
            }
        }
    }

2.升级版0-1背包问题

对于一组不同重量、不同价值、不可分割的物品,我们选择将某些物品装入背包,在满足背包最大重量限制的前提下,背包中可装入物品的总价值最大是多少呢?

(1)回溯解法

    private static int maxV = Integer.MIN_VALUE; // 结果放到maxV中
    private static int[] items = {2, 2, 4, 6, 3};  // 物品的重量
    private static int[] value = {3, 4, 8, 9, 6}; // 物品的价值
    private static int n = 5; // 物品个数
    private static int w = 9; // 背包承受的最大重量

    public static void f(int i, int cw, int cv) {
        if (i == n || cw == w) {
            if (maxV < cv) {
                maxV = cv;
            }
            return;
        }
        f(i + 1, cw, cv);
        if (cw + items[i] <= w) {
            f(i + 1, cw + items[i], cv + value[i]);
        }
    }

(2)动态规划解法

    private static int maxV = Integer.MIN_VALUE; // 结果放到maxV中
    private static int[] items = {2, 2, 4, 6, 3};  // 物品的重量
    private static int[] value = {3, 4, 8, 9, 6}; // 物品的价值
    private static int n = 5; // 物品个数
    private static int w = 9; // 背包承受的最大重量

    public static void dpF(int[] weight, int n, int[] value, int w) {
        int[][] state = new int[n][w + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= w; j++) {
                state[i][j] = -1;
            }
        }
        state[0][0] = 0;
        if (weight[0] <= w) {
            state[0][weight[0]] = value[0];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= w; j++) {
                if (state[i - 1][j] >= 0) {
                    state[i][j] = state[i - 1][j];
                }
            }
            for (int j = 0; j <= w - weight[i]; j++) {
                if (state[i - 1][j] >= 0) {
                    int v = state[i - 1][j] + value[i];
                    if (v > state[i][j + weight[i]]) {
                        state[i][j + weight[i]] = v;
                    }
                }
            }
        }
        int maxVal = Integer.MIN_VALUE;
        for (int j = 0; j <= w; j++) {
            if (state[n - 1][j] > maxVal) {
                maxVal = state[n - 1][j];
            }
        }
        System.out.println("最大值为:" + maxVal);
    }

使用一维数组降低空间消耗:

    private static int maxV = Integer.MIN_VALUE; // 结果放到maxV中
    private static int[] items = {2, 2, 4, 6, 3};  // 物品的重量
    private static int[] value = {3, 4, 8, 9, 6}; // 物品的价值
    private static int n = 5; // 物品个数
    private static int w = 9; // 背包承受的最大重量

    public static void dpF(int[] weight, int n, int[] value, int w) {
        int[] state = new int[w + 1];
        for (int j = 0; j <= w; j++) {
            state[j] = -1;
        }
        state[0] = 0;
        if (weight[0] <= w) {
            state[weight[0]] = value[0];
        }
        for (int i = 1; i < n; i++) {
            for (int j = w - weight[i]; j >= 0; j--) {
                if (state[j] >= 0) {
                    int v = state[j] + value[i];
                    if (v > state[j + weight[i]]) {
                        state[j + weight[i]] = v;
                    }
                }
            }
        }
        int maxVal = Integer.MIN_VALUE;
        for (int j = 0; j <= w; j++) {
            if (state[j] > maxVal) {
                maxVal = state[j];
            }
        }
        System.out.println("最大值为:" + maxVal);
    }

3.杨辉三角

“杨辉三角”现在对它进行一些改造:每个位置的数字可以随意填写,经过某个数字只能到达下面一层相邻的两个数字。假设你站在第一层,往下移动,我们把移动到最底层所经过的所有数字之和,定义为路径的长度。请求出从最高层移动到最底层的最短路径长度。


(1)回溯解法

    public static void yanghuiTriangle(int[][] matrix, int i, int j, int currLevel, int totalLevel, int dist) {
        dist = dist + matrix[i][j];//加上当前的结点才是该层的值
        if (currLevel == (totalLevel - 1)) {
            if (dist < minDist) {
                minDist = dist;
            }
            return;
        }

        if (i + 1 < totalLevel) {
            yanghuiTriangle2(matrix, i + 1, j, currLevel + 1, totalLevel, dist);
            int nextLen = matrix[i + 1].length;
            if (j + 1 < nextLen) {
                yanghuiTriangle2(matrix, i + 1, j + 1, currLevel + 1, totalLevel, dist);
            }
        }
    }

    public static void main(String[] args) {
        int[][] matrix = {{5}, {7, 8}, {2, 3, 4}, {4, 9, 6, 1}, {2, 7, 9, 4, 5}};//杨辉三角每一层的数字
        yanghuiTriangle(matrix, 0, 0, 0, matrix.length, 0);
        System.out.println(minDist);
    }

(2)动态规划解法

状态转移方程:
f(i,j) = matrix(i,j) + min(f(i-1,j),f(i-1,j-1))
状态转移表:
括号中对应matrix中原来的值

状态转移表.png

    private static void yanghuiTriangle(int[][] matrix) {
        if (matrix == null) return;
        int[][] state = new int[matrix.length][matrix.length];
        state[0][0] = matrix[0][0];//初始化第一行
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                int min = Integer.MAX_VALUE;
                if (j < matrix[i - 1].length) {
                    min = state[i - 1][j];
                }
                if (j - 1 >= 0) {
                    min = Math.min(min, state[i - 1][j - 1]);
                }
                state[i][j] = min + matrix[i][j];
            }
        }
        int min = Integer.MAX_VALUE;
        for (int j = 0; j < state.length - 1; j++) {
            if (state[state.length - 1][j] < min) {
                min = state[state.length - 1][j];
            }
        }
        System.out.println("从顶层到底层最短路径为:" + min);
    }

使用一维数组降低空间消耗:

    private static void yanghuiTriangle(int[][] matrix) {
        if (matrix == null) return;
        int[] state = new int[matrix.length];//保存每一层最短路径
        state[0] = matrix[0][0];//初始化第一行
        for (int i = 1; i < matrix.length; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < matrix[i].length; j++) {
                if (j < matrix[i - 1].length) {
                    min = Math.min(min, matrix[i - 1][j]);
                }
                if (j - 1 >= 0) {
                    min = Math.min(min, matrix[i - 1][j - 1]);
                }
            }
            state[i] = state[i - 1] + min;
        }
        System.out.println("从顶层到底层最短路径为:" + state[matrix.length - 1]);
    }

4.矩阵最短距离

假设有一个 n 乘以 n 的矩阵 w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上角,终止位置在右下角。将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角,会有很多不同的路径可以走。我们把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少呢?


(1)回溯解法

    private static int min = Integer.MAX_VALUE;

    public static void minDist(int[][] w, int i, int j, int dist, int n) {
        if (i == (n - 1) && j == (n - 1)) {
            if (dist + w[i][j] < min) {
                min = dist + w[i][j];
            }
            return;
        }
        if (i < n - 1) {
            minDist(w, i + 1, j, dist + w[i][j], n);//向下走
        }

        if (j < n - 1) {
            minDist(w, i, j + 1, dist + w[i][j], n);//向右走
        }
    }

(2)动态规划解法

状态转移表法:
    public static void minDistDp(int[][] matrix, int n) {
        int[][] state = new int[n][n];
        state[0][0] = matrix[0][0];
        for (int j = 1; j < n; j++) {//初始化第一行
            state[0][j] = state[0][j - 1] + matrix[0][j];
        }
        for (int i = 1; i < n; i++) {//初始化第一列
            state[i][0] = state[i - 1][0] + matrix[i][0];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                state[i][j] = matrix[i][j] + Math.min(state[i - 1][j], state[i][j - 1]);
            }
        }
        System.out.println("min val from (0,0) To (n-1,n-1):" + state[n - 1][n - 1]);
    }

    public static void main(String[] args) {
        int n = 4;
        int[][] w = {{1, 3, 5, 9}, {2, 1, 3, 4}, {5, 2, 6, 7}, {6, 8, 4, 3}};
        minDistDp(w, n);
    }
状态转移方程法:

状态转移方程:min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))

递归加“备忘录”:

    private static int n = 5;
    private static int[][] mem = new int[n][n];
    private static int[][] matrix = {{1, 3, 5, 9}, {2, 1, 3, 4}, {5, 2, 6, 7}, {6, 8, 4, 3}};
    
    public static int minDistDp2(int i, int j) {
        if (i == 0 && j == 0) {//递归终止条件
            return matrix[0][0];
        }
        if (mem[i][j] > 0) {
            return mem[i][j];
        }
        int curMinUp = Integer.MAX_VALUE;
        if (i - 1 >= 0) {
            curMinUp = minDistDp2(i - 1, j);
        }
        int curMinLeft = Integer.MAX_VALUE;
        if (j - 1 >= 0) {
            curMinLeft = minDistDp2(i, j - 1);
        }
        int curMinDist = matrix[i][j] + Math.min(curMinLeft, curMinUp);
        mem[i][j] = curMinDist;
        return curMinDist;
    }

    public static void main(String[] args) {
        System.out.println(minDistDp2(n - 1, n - 1));
    }

5.硬币找零问题

假设我们有几种不同币值的硬币 v1,v2,……,vn(单位是元)。如果我们要支付 w 元,求最少需要多少个硬币。
比如,我们有 3 种不同的硬币,1 元、3 元、5 元,我们要支付 9 元,最少需要 3 个硬币(3 个 3 元的硬币)。

(1)回溯解法

    private static int minCoin = Integer.MAX_VALUE;

    public static void f(int[] money, int total, int num) {
        if (total == 0) {
            if (num < minCoin) {
                minCoin = num;
            }
            return;
        }
        for (int m : money) {//一种硬币可以使用多次
            if (total - m >= 0) {
                f(money, total - m, num + 1);
            }
        }
    }

(2)动态规划解法

    public static void countMoneyMin(int[] money, int total) {
        int maxLevel = total / money[0];
        int[][] state = new int[maxLevel][total + 1];
        for (int i = 0; i < money.length; i++) {
            if (money[i] <= total) {
                state[0][money[i]] = money[i];
            }
        }
        int num = 0;
        if (state[0][total] > 0) {
            num = 1;
        }
        if (num == 0) {
            for (int i = 1; i < maxLevel; i++) {
                for (int j = 0; j <= total; j++) {
                    if (state[i - 1][j] > 0) {
                        for (int k : money) {
                            if (j + k <= total) {
                                state[i][j + k] = k;
                            }
                        }
                    }
                }
                if (state[i][total] > 0) {//已经找到了
                    num = i + 1;
                    break;
                }

            }
        }

        System.out.println(num);
        int j = total;
        for (int i = num - 1; i >= 0; i--) {
            if (state[i][j] > 0) {
                System.out.print("choose:" + state[i][j] + ",");
                j = j - state[i][j];
            }
        }
    }

使用一维数组优化空间复杂度:

    public int getLeastCoinNumByDP(int[] coinVal, int total) {
        // coinNum存放的是每个对应金额下最少硬币的最优解
        int coinNum[] = new int[total + 1];
        //初始化coinNum数组,硬币值数组对应的值的硬币数量都为1
        for (int i = 0; i < coinVal.length; i++) {
            coinNum[coinVal[i]] = 1;
        }

        for (int i = 1; i <= total; i++) {
            if (coinNum[i] == 0) {
                int minTemp = Integer.MAX_VALUE; // 获取每个i对应的最小硬币数值
                for (int j = 0; j < coinVal.length; j++) {
                    if (i - coinVal[j] > 0) {
                        int v1 = coinNum[i - coinVal[j]] + 1;
                        if (v1 < minTemp) {
                            minTemp = v1;
                        }
                    }
                }
                coinNum[i] = minTemp;
            }
        }
        return coinNum[total];
    }

参考:
[1]40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?-极客时间
[2]41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题-极客时间

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 219,366评论 6 508
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,521评论 3 395
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 165,689评论 0 356
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,925评论 1 295
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,942评论 6 392
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,727评论 1 305
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,447评论 3 420
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,349评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,820评论 1 317
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,990评论 3 337
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,127评论 1 351
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,812评论 5 346
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,471评论 3 331
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,017评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,142评论 1 272
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,388评论 3 373
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 45,066评论 2 355

推荐阅读更多精彩内容