动态规划——坐标型&位操作型

朴灿烈づ我的快乐病毒、 2023-06-20 09:13 12阅读 0赞

# 动态规划——坐标型&位操作型 #

--------------------

1.  坐标型动态规划——带阻碍的唯一路径
2.  序列型动态规划——油漆房子
3.  划分型动态规划——解密方式
4.  坐标型动态规划——最长上升连续子序列
5.  坐标型动态规划——最小路径和
6.  坐标型动态规划——炸弹袭击
7.  位操作型动态规划——计算二进制中 1 的个数

--------------------

### 1. 坐标型动态规划——带阻碍的唯一路径 ###

[https://www.lintcode.com/problem/unique-paths-ii/description][https_www.lintcode.com_problem_unique-paths-ii_description]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]  
题目描述：

*  给定 m 行 n 列的网格，有一个机器人从左上角（0,0）出发，每一步可以向下或者向右走一步。
 *  网格中有些地方有障碍，机器人不能通过障碍格。
 *  问有多少种不同的方式走到右下角？  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]

public int uniquePathsWithObstacles(int[][] board) {
        
            int m = board.length;
            int n = board[0].length;
            if (m == 0 || n == 0) {
        
                return 0;
            }
    
            int[][] f = new int[m][n];
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (board[i][j] == 1) {
        
                        f[i][j] = 0;
                        continue;
                    }
                    if (i == 0 || j == 0) {
        
                        f[i][j] = 1;
                        continue;
                    }
                    if (i > 0) {
        
                        f[i][j] += f[i - 1][j];
                    }
                    if (j > 0) {
        
                        f[i][j] += f[i][j - 1];
                    }
                }
            }
            return f[m - 1][n - 1];
        }

--------------------

### 2. 序列型动态规划——油漆房子 ###

[https://www.lintcode.com/problem/paint-house/description][https_www.lintcode.com_problem_paint-house_description]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]  
题目描述：

*  有一排 N 栋房子，每栋房子要涂成 3 种颜色中的一种：红、蓝、绿。
 *  任何两栋相邻房子不能涂成相同的颜色
 *  第 i 栋房子染成红色、蓝色、绿色的花费分别是 cost\[i\]\[0\]，cost\[i\]\[1\]，cost\[i\]\[2\]
 *  问最少需要花多少钱油漆这些房子？

public int minCost(int[][] c) {
        
            int n = c.length;
            if (n == 0) {
        
                return 0;
            }
    
            int[][] f = new int[n + 1][3];
            f[0][0] = f[0][1] = f[0][2] = 0;
            for (int i = 1; i <= n; i++) {
        
                for (int j = 0; j < 3; j++) {
        
                    f[i][j] = Integer.MAX_VALUE;
                    for (int k = 0; k < 3; k++) {
        
                        if (j != k) {
        
                            f[i][j] = Math.min(f[i][j], f[i - 1][k] + c[i - 1][j]);
                        }
                    }
                }
            }
            return Math.min(f[n][0], Math.min(f[n][1], f[n][2]));
        }

--------------------

### 3. 划分型动态规划——解密方式 ###

[https://www.lintcode.com/problem/decode-ways/description][https_www.lintcode.com_problem_decode-ways_description]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 3]  
题目描述：

*  有一段由 A-Z 组成的字符串信息被加密成数字串。
 *  加密方式为：A->1, B->2, …Z->26
 *  给定加密后的数字串 S\[0…N-1\]，问有多少种方式解密成字符串？

public int numDecodings(String ss) {
        
            char[] s = ss.toCharArray();
            int n = s.length;
            if (n == 0) {
        
                return 0;
            }
    
            int[] f = new int[n + 1];
            f[0] = 1;
            int i, j;
            for (i = 1; i <= n; i++) {
        
                f[i] = 0;
                if (s[i - 1] >= '1' && s[i - 1] <= '9') {
        
                    f[i] += f[i - 1];
                }
    
                if (i > 1) {
        
                    j = 10 * (s[i - 2] - '0') + (s[i - 1] - '0');
                    if (j >= 10 && j <= 26) {
        
                        f[i] += f[i - 2];
                    }
                }
            }
            return f[n];
        }

--------------------

### 4. 坐标型动态规划——最长上升连续子序列 ###

题目描述：

*  给定 a\[0\],…,a\[n-1\]
 *  找到最长的连续子序列 i，i+1，i+2，…j，使得 a\[i\] < a\[i+1\] < a\[j\]，或者 a\[i\] > a\[i+1\] > …>a\[j\]，输出长度 j-i+1.

> 例子：  
> 输入：\[5,1,2,3,4\]  
> 输出：4（子序列 1,2,3,4）

public int longestIncreasingContinuousSubsequence(int[] nums) {
        
            int n = nums.length;
            if (n == 0) {
        
                return 0;
            }
            int r1 = LIS(nums, n);
            //reverse
            int i, j, temp;
            i = 0;
            j = n - 1;
            while (i < j) {
        
                temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++;
                j--;
            }
            int r2 = LIS(nums, n);
            return r1 >= r2 ? r1 : r2;
        }
    
        private int LIS(int[] nums, int n) {
        
            int i;
            int[] f = new int[n];
            int res = 0;
            for (i = 0; i < n; i++) {
        
                f[i] = 1;
                if (i > 0 && nums[i] > nums[i - 1]) {
        
                    f[i] = f[i - 1] + 1;
                }
                res = Math.max(res, f[i]);
            }
            return res;
        }

--------------------

### 5. 坐标型动态规划——最小路径和 ###

[https://www.lintcode.com/problem/minimum-path-sum/description][https_www.lintcode.com_problem_minimum-path-sum_description]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 4]  
题目描述：

*  给定 m 行 n 列的网格，每个格子（i，j）里都一个非负数 A\[i\]\[j\]
 *  求一个左上角（0,0）到右下角的路径，每一步只能向下或者向右走一步，使得路径上的格子里的数字之和最小
 *  输出最小数字和  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 5]

public int minPathSum(int[][] board) {
        
            int m = board.length;
            int n = board[0].length;
            if (m == 0 || n == 0) {
        
                return 0;
            }
    
            int[][] f = new int[m][n];
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (i == 0 && j == 0) {
        
                        f[i][j] = board[0][0];
                        continue;
                    }
                    int t = Integer.MAX_VALUE;
                    if (i > 0) {
        
                        t = Math.min(t, f[i - 1][j] );
                    }
                    if (j > 0) {
        
                        t = Math.min(t, f[i][j - 1] );
                    }
                    f[i][j] = t+board[i][j];
                }
            }
            return f[m-1][n-1];
        }

滚动数组方式：将 f 的 i 位置 %2.

public int minPathSum(int[][] board) {
        
            int m = board.length;
            int n = board[0].length;
            if (m == 0 || n == 0) {
        
                return 0;
            }
    
            int[][] f = new int[2][n];
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (i == 0 && j == 0) {
        
                        f[i % 2][j] = board[0][0];
                        continue;
                    }
                    int t = Integer.MAX_VALUE;
                    if (i > 0) {
        
                        t = Math.min(t, f[1 - i % 2][j]);
                    }
                    if (j > 0) {
        
                        t = Math.min(t, f[i % 2][j - 1]);
                    }
                    f[i % 2][j] = t + board[i][j];
                }
            }
            return f[(m - 1) % 2][n - 1];
        }

--------------------

### 6. 坐标型动态规划——炸弹袭击 ###

[https://www.lintcode.com/problem/bomb-enemy/description][https_www.lintcode.com_problem_bomb-enemy_description]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 6]  
题目描述：

*  有一个 M\*N 的网格，每个格子可能是空的，可能有一个敌人，可能有一堵墙
 *  只能在某个空格子里放一个炸弹，炸弹会炸死所有同行同列的敌人，但是不能穿透墙
 *  最多能炸死几个敌人

public int maxKilledEnemies(char[][] A) {
        
            if (A == null || A.length == 0 || A[0].length == 0) {
        
                return 0;
            }
    
            int m = A.length;
            int n = A[0].length;
            int[][] up = new int[m][n];
            int[][] down = new int[m][n];
            int[][] left = new int[m][n];
            int[][] right = new int[m][n];
            int i, j, t;
    
            for (i = 0; i < m; ++i) {
        
                for (j = 0; j < n; ++j) {
        
                    up[i][j] = 0;
                    if (A[i][j] != 'W') {
        
                        if (A[i][j] == 'E') {
        
                            up[i][j] = 1;
                        }
    
                        if (i - 1 >= 0) {
        
                            up[i][j] += up[i-1][j];
                        }
                    }
                }
            }
    
            for (i = m - 1; i >= 0; --i) {
        
                for (j = 0; j < n; ++j) {
        
                    down[i][j] = 0;
                    if (A[i][j] != 'W') {
        
                        if (A[i][j] == 'E') {
        
                            down[i][j] = 1;
                        }
    
                        if (i + 1 < m) {
        
                            down[i][j] += down[i+1][j];
                        }
                    }
                }
            }
    
            for (i = 0; i < m; ++i) {
        
                for (j = 0; j < n; ++j) {
        
                    left[i][j] = 0;
                    if (A[i][j] != 'W') {
        
                        if (A[i][j] == 'E') {
        
                            left[i][j] = 1;
                        }
    
                        if (j - 1 >= 0) {
        
                            left[i][j] += left[i][j-1];
                        }
                    }
                }
            }
    
            for (i = 0; i < m; ++i) {
        
                for (j = n - 1; j >= 0; --j) {
        
                    right[i][j] = 0;
                    if (A[i][j] != 'W') {
        
                        if (A[i][j] == 'E') {
        
                            right[i][j] = 1;
                        }
    
                        if (j + 1 < n) {
        
                            right[i][j] += right[i][j+1];
                        }
                    }
                }
            }
    
            int res = 0;
            for (i = 0; i < m; ++i) {
        
                for (j = 0; j < n; ++j) {
        
                    if (A[i][j] == '0') {
        
                        t = up[i][j] + down[i][j] + left[i][j] + right[i][j];
                        res = Math.max(res,t);
                    }
                }
            }
    
            return res;
        }

--------------------

### 7. 位操作型动态规划——计算二进制中 1 的个数 ###

[https://www.lintcode.com/problem/counting-bits/description][https_www.lintcode.com_problem_counting-bits_description]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 7]  
题目描述：

*  给定 N，要求输出 0,1，…，N 的每个数的二进制表示里1 的个数。

public int[] countBits(int num) {
        
            int[] f = new int[num + 1];
            f[0] = 0;
            for (int i = 1; i <= num; i++) {
        
                f[i] = (i % 2) + f[i >> 1];
            }
            return f;
        }

[https_www.lintcode.com_problem_unique-paths-ii_description]: https://www.lintcode.com/problem/unique-paths-ii/description
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191209175952775.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191209181153777.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[https_www.lintcode.com_problem_paint-house_description]: https://www.lintcode.com/problem/paint-house/description
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191209200748354.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[https_www.lintcode.com_problem_decode-ways_description]: https://www.lintcode.com/problem/decode-ways/description
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2019120921100361.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[https_www.lintcode.com_problem_minimum-path-sum_description]: https://www.lintcode.com/problem/minimum-path-sum/description
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191210152117306.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20191210152547875.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[https_www.lintcode.com_problem_bomb-enemy_description]: https://www.lintcode.com/problem/bomb-enemy/description
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20191210173808477.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[https_www.lintcode.com_problem_counting-bits_description]: https://www.lintcode.com/problem/counting-bits/description
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20191212105608274.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70