动态规划(中篇)

Bertha 。 2023-10-04 18:33 14阅读 0赞

**第四题: 路径总数**

[不同路径的数目(一)\_牛客题霸\_牛客网][Link 1]

### 描述 ###

![b3d9442cdb294785868777ca5d6f23da.png][]

一个机器人在m×n大小的地图的左上角（起点）。

机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。

可以有多少种不同的路径从起点走到终点？

**将上图处理一下后:**

![c16f5c5daa1440f68729e6892ddbd5a4.png][]

问题 : 上图4\*5大小的地图,到达终点有多少不同的路径

**状态: F(i,j): 从(0,0) 到达 (i,j) 的路径个数**

**状态转移方程: 推导下**

**以图中橙色(i,j) 为例 F(1,2) = F(1,1) + F(0,2) = 2 + 1 = 3**

**所以 F(i,j): F(i,j-1) + F(i-1,j)**

**初始状态: F(i,0) = F(0,j) = 1**

**返回: F(m-1,n-1)**

public class Solution {
            public int uniquePaths(int m, int n) {
                List<List<Integer>> pathNum = new ArrayList<>();
                // 申请F(i,j)空间，初始化
                for(int i = 0; i < m; ++i){
                    pathNum.add(new ArrayList<>());
                    pathNum.get(i).add(1);
                }
                for(int i = 1; i < n; ++i){
                    pathNum.get(0).add(1);
                }
                for(int i = 1; i < m; ++i){
                    for(int j = 1; j < n; ++j){
                // F(i,j) = F(i-1,j) + F(i,j-1)
                        pathNum.get(i).add(pathNum.get(i).get(j - 1)
                                + pathNum.get(i - 1).get(j));
                    }
                }
                return pathNum.get(m - 1).get(n - 1);
            }
        }

第五题: 最小路径和

[带权值的最小路径和\_牛客题霸\_牛客网][Link 2]

### 描述 ###

给定一个由非负整数填充的m x n的二维数组，现在要从二维数组的左上角走到右下角，请找出路径上的所有数字之和最小的路径。  
注意：你每次只能向下或向右移动。

输入：\[\[1,2\],\[5,6\],\[1,1\]\]

返回值：8

![af96a8ff644b4b92a170a3e6e4cdf77e.png][]

**状态:F(i,j): 从(0,0) 到达 (i,j) 的最短路径和**

**转移方程:**

**F(i,j): min(F(i,j-1), F(i-1,j)) + arr\[i\]\[j\]**

**第一行: F(0,j): F(0,j-1) + arr\[0\]\[j\]**

**第一列: F(i,0): F(i-1,0) + arr\[i\]\[0\]**

**初始状态:**

**F(0,0) = arr\[0\]\[0\]**

**返回:**

**F(row-1, col-1)**

public class Solution {
        public int minPathSum(int[][] grid) {
            int row = grid.length;
            int col = grid[0].length;
             如果为空或者只有一行，返回0
            if(row == 0 || col == 0) {
                return 0;
            }
            // F(0,0), F(0,i), F(i,0)初始化
            for(int i = 1;i < row;i++) {
                grid[i][0] = grid[i - 1][0] + grid[i][0];
            }
            for(int i = 1;i < col;i++) {
                grid[0][i] = grid[0][i - 1] + grid[0][i];
            }
            // F(i,j) = min{F(i-1,j) , F(i,j-1)} + (i,j)
            for(int i = 1;i < row;i++) {
                for(int j = 1;j < col;j++) {
                    grid[i][j] = Math.min(grid[i - 1][j],grid[i][j - 1]) + grid[i][j];
                }
            }
            return grid[row - 1][col - 1];
        }
    }

第六题: 背包问题

[LintCode 炼码][LintCode]

描述

有 `n` 个物品和一个大小为 `m` 的背包. 给定数组 `A` 表示每个物品的大小和数组 `V` 表示每个物品的价值.

问最多能装入背包的总价值是多大?

1.  `A[i], V[i], n, m` 均为整数
2.  你不能将物品进行切分
3.  你所挑选的要装入背包的物品的总大小不能超过 `m`
4.  每个物品只能取一次
5.  m <= 1000m<=1000

输入：

m = 10
    A = [2, 3, 5, 7]
    V = [1, 5, 2, 4]

输出：9

**解题四板斧**

**状态：  
F(i, j): 前i个物品放入大小为j的背包中所获得的最大价值  
状态递推：对于第i个商品，有一种例外，装不下，两种选择，放或者不放  
如果装不下：此时的价值与前i-1个的价值是一样的  
F(i,j) = F(i-1,j)  
如果可以装入：需要在两种选择中找最大的  
F(i, j) = max\{F(i-1,j), F(i-1, j - A\[i\]) + V\[i\]\}  
F(i-1,j): 表示不把第i个物品放入背包中， 所以它的价值就是前i-1个物品放入大小为j的背包的最大价值  
F(i-1, j - A\[i\]) + V\[i\]：表示把第i个物品放入背包中，价值增加V\[i\],但是需要腾出j - A\[i\]的大小放第i个商品  
初始化： 第0行和第0列都为0，表示没有装物品时的价值都为0  
F(0,j) = F(i,0) = 0  
返回值： F(n,m)**

**可能文字不好理解,直接上图**

**![2876586083094002b3fbc541ce6199db.png][]**

public int backPackII(int m, int[] A, int[] V) {
            // write your code here
            int num = A.length;
            if(m == 0 || num == 0)
                return 0;
            //多加一行一列，用于设置初始条件
            int[][] maxValue = new int[num + 1][m + 1];
            //初始化所有位置为0，第一行和第一列都为0，初始条件
            for(int i = 0; i <= num; ++i){
                maxValue[i][0] = 0;
            }
            for(int i = 1; i <= m; ++i){
                maxValue[0][i] = 0;
            }
            for(int i = 1; i <= num; ++i){
                for(int j = 1; j <= m; ++j){
                    //第i个商品在A中对应的索引为i-1: i从1开始
                    //如果第i个商品大于j,说明放不下， 所以(i,j)的最大价值和(i-1,j)相同
                    if(A[i - 1] > j){
                        maxValue[i][j] = maxValue[i - 1][j];
                    }
                    else{
                            //如果可以装下，分两种情况，装或者不装
                        //如果不装，则即为(i-1, j)
                        //如果装，需要腾出放第i个物品大小的空间： j - A[i-1],装入之后的最大价值
                        //即为(i -1, j - A[i-1]) + 第i个商品的价值V[i - 1]
                        //最后在装与不装中选出最大的价值
                        int newValue = maxValue[i - 1][j - A[i - 1]]
                                + V[i - 1];
                        maxValue[i][j] = Math.max(newValue
                                , maxValue[i - 1][j]);
                    }
                }
            }
            //返回装入前N个商品，物品大小为m的最大价值
            return maxValue[num][m];
        }
    }

[Link 1]: https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358?tpId=46&tqId=29117&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
[b3d9442cdb294785868777ca5d6f23da.png]: https://img-blog.csdnimg.cn/b3d9442cdb294785868777ca5d6f23da.png
[c16f5c5daa1440f68729e6892ddbd5a4.png]: https://img-blog.csdnimg.cn/c16f5c5daa1440f68729e6892ddbd5a4.png
[Link 2]: https://www.nowcoder.com/practice/23462ed010024fcabb7dbd3df57c715e?tpId=46&tqId=29115&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
[af96a8ff644b4b92a170a3e6e4cdf77e.png]: https://img-blog.csdnimg.cn/af96a8ff644b4b92a170a3e6e4cdf77e.png
[LintCode]: https://www.lintcode.com/problem/backpack-ii/description
[2876586083094002b3fbc541ce6199db.png]: https://img-blog.csdnimg.cn/2876586083094002b3fbc541ce6199db.png