区块链技术博客
www.b2bchain.cn

算法-动态规划

这篇文章主要介绍了算法-动态规划,通过具体代码讲解6031并且分析了算法-动态规划的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了算法-动态规划。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/?p=6031。具体如下:

算法 动态规划

算法

发布日期:   2019-12-02
文章字数:   2k
阅读时长:   9 分
阅读次数:  

动态规划解题模版::坐标型

坐标型dp一般都是给定网格、序列,来求满足某种性质的最大值、最小值。开数组时,f[i]代表以ai 结尾的满足条件的子序列,f[i][j]代表以i、j结尾的满足条件的某种情况。

做题思路:

  • 从最后一步出发思考,确定状态
  • 分析子问题是什么
  • 得到状态转移方程
  • 确定初始条件与边界条件
  • 编程

1、Lintcode 114 UniquePaths

【问题】有一个机器人的位于一个 m × n个网格左上角。机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。问有多少条不同的路径?

【分析】最后一步:要么从左边来,要么从上边来,故dp[i][j] = dp[i][j-1] + dp[i-1][j]

public int uniquePaths(int m, int n) {         int[][] dp = new int[m][n];         //初始化         dp[0][0] = 1;         //初始化第一行         for (int j = 0; j < n; j++) {             dp[0][j] = 1;         }         //初始化第一列         for (int i = 0; i < m; i++) {             dp[i][0] = 1;         }         //处理其他         for (int i = 1; i < m; i++) {             for (int j = 1; j < n; j++) {                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];             }         }         return dp[m - 1][n - 1];     }

2、Lintcode 115 UniquePathsWithObstacles

【问题】上一题的跟进问题,现在考虑网格中有障碍物,那样将会有多少条不同的路径?网格中的障碍和空位置分别用 1 和 0 来表示。

【分析】从最后一步出发,要选一条没有障碍的路径到达右下角,当前位置i,j所有可能路径依然是 dp[i] [j] = dp[i] [j-1] + dp[i-1] [j],但必须是没有障碍的

  • 起点和终点若有障碍,直接返回0
  • 初始化第一行和第一列,也要考虑有障碍的情况
  • 起点和终点没有障碍,若途中碰到障碍了,令dp[i][j] = 0,表示不可达
public int uniquePathsWithObstacles(int[][] A) {         int n = A.length;         int m = A[0].length;          //判断起点和终点有没有障碍,有障碍直接返回0         if (A[0][0] == 1 || A[n - 1][m - 1] == 1) {             return 0;         }         int[][] dp = new int[n][m];         //初始化         dp[0][0] = 1;         int i, j;         //初始化第一行         for (j = 1; j < m; j++) {             if (A[0][j] == 1) {                 dp[0][j] = 0;             } else {                 dp[0][j] = dp[0][j - 1];             }         }         //初始化第一列         for (i = 1; i < n; i++) {             if (A[i][0] == 1) {                 dp[i][0] = 0;             } else {                 dp[i][0] = dp[i - 1][0];             }         }         //处理其他         for (i = 1; i < n; i++) {             for (j = 1; j < m; j++) {                 if (A[i][j] == 1) {                     dp[i][j] = 0;                     continue;                 } else {                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1];                 }              }         }         return dp[n - 1][m - 1];     }

3、Lintcode 397 Longest Increasing Continuous Subsequence

【问题】给定一个整数数组(下标从 0 到 n-1, n 表示整个数组的规模),请找出该数组中的最长上升连续子序列。(最长上升连续子序列可以定义为从右到左或从左到右的序列。)

【分析】也就是求“最长连续单调子序列”,也就是LIS+LDS。实际上只要求个LIS再倒过来求一遍。

public int longestIncreasingContinuousSubsequence(int[] A) {         int res = LIS(A);          //倒过来求一遍         int i = 0;         int j = A.length - 1;         while (i < j) {             int temp = A[i];             A[i] = A[j];             A[j] = temp;             i++;             j--;         }         return Math.max(res, LIS(A));     }      public int LIS(int[] A) {         int n = A.length;         if (n == 0) {             return 0;         }         int[] dp = new int[n];         int res = 1;        //最少长度是1         dp[0] = 1;            for (int i = 1; i < n; i++) {             //长度至少是1,它本身             dp[i] = 1;             if (A[i] > A[i - 1]) {                 dp[i] = dp[i - 1] + 1;             }             res = Math.max(res, dp[i]);         }         return res;     }

4、LintCode 110 Minimum Path Sum

【问题】给定一个只含非负整数的m x n网格,找到一条从左上角到右下角的可以使数字和最小的路径。简而言之求最小路径和。

//普通方式 public int minPathSum(int[][] A) {         int n = A.length;         int m = A[0].length;         int[][] dp = new int[n][m];          for (int i = 0; i < n; i++) {             for (int j = 0; j < m; j++) {                 if (i == 0 && j == 0) {                     dp[i][j] = A[0][0];                     continue;                 }                 dp[i][j] = Integer.MAX_VALUE;                 //来自上方的情况                 if (i > 0) {                     dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + A[i][j]);                 }                 //来自左侧的情况                 if (j > 0) {                     dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + A[i][j]);                 }             }         }         return dp[n-1][m - 1];     }

使用滚动数组进行优化,当前行只和上面一行有关系,实际上只需要开两行,使用oldnew指针,old存放i-1行,new存放当前第i行,关键语句在于old和now进行交换

old = now;

now = 1 – now

//滚动数组优化 //只需要把i变为now,i-1变为old即可 public int minPathSum(int[][] A) {         int n = A.length;         int m = A[0].length;         int[][] dp = new int[2][m];         int old = 0, now = 0;          for (int i = 0; i < n; i++) {             old = now;             now = 1 - now;             for (int j = 0; j < m; j++) {                 if (i == 0 && j == 0) {                     dp[now][j] = A[0][0];                     continue;                 }                 dp[now][j] = Integer.MAX_VALUE;                 //来自上方                 if (i > 0) {                     dp[now][j] = Math.min(dp[now][j], dp[old][j] + A[i][j]);                 }                 //来自左侧                 if (j > 0) {                     dp[now][j] = Math.min(dp[now][j], dp[now][j - 1] + A[i][j]);                 }             }         }         return dp[now][m - 1];     }

算法-动态规划

5、LintCode 553 Bomb Enemy

【问题】给定一个二维矩阵, 每一个格子可能是一堵墙 W,或者 一个敌人 E 或者空 0 (数字 ‘0’), 返回你可以用一个炸弹杀死的最大敌人数. 炸弹会杀死所有在同一行和同一列没有墙阻隔的敌人。 由于墙比较坚固,所以墙不会被摧毁。

【分析】原本只能在空地放炸弹,现在假设有敌人和有墙的地方也能放炸弹,有敌人的地方,格子里的敌人能被炸死,再加上其他炸死的人,有墙的地方,炸死人数为0。现在分析一个方向,比如向上,有三种情况:

  • (i,j)是空地:结果就是从(i-1,j)格开始向上能炸死的敌人数
  • (i,j)是敌人:结果就是从(i-1,j)格开始向上能炸死的敌人数 + 1
  • (i,j)是墙:0

原来要求(i,j)格子放炸弹向上能炸死的敌人数,子问题就转化为(i-1,j)格向上能炸死的敌人数,上述三种情况就如下:

  • Up[i][j] = Up[i-1][j],(i,j)是空地的情况
  • Up[i][j] = Up[i-1][j] + 1,(i,j)是敌人的情况
  • Up[i][j] = 0,(i,j)是墙的情况

初始条件就是第0行,如果是敌人,向上炸死人数为1,如果是空地或墙,向上炸死人数为0。

另外三个方向Down[i][j], Left[i][j], Right[i][j]也是一样考虑。炸死的敌人数就是四个方向加起来,每次更新一下最大值。

public static int maxKilledEnemies(char[][] grid) {         if (grid == null || grid.length == 0 || grid[0].length == 0) {             return 0;         }         int m = grid.length;         int n = grid[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[][] dp = new int[m][n];          for (int i = 0; i < m; i++) {             for (int j = 0; j < n; j++) {                 //i,j处为炸弹放置的位置                 //如果是墙,其实四种情况都是0                 if (grid[i][j] == 'W') {                     up[i][j] = 0;                     continue;                 }                 up[i][j] = grid[i][j] == 'E' ? 1 : 0;                 if (i > 0) {                     up[i][j] += up[i - 1][j];                 }             }         }          //down应该从下往上算,自底向上         for (int i = m - 1; i >= 0; i--) {             for (int j = 0; j < n; j++) {                 if (grid[i][j] == 'W') {                     down[i][j] = 0;                     continue;                 }                 down[i][j] = grid[i][j] == 'E' ? 1 : 0;                 if (i < m - 1) {                     down[i][j] += down[i + 1][j];                 }             }         }          //left,从左往右算         for (int i = 0; i < m; i++) {             for (int j = 0; j < n; j++) {                 if (grid[i][j] == 'W') {                     left[i][j] = 0;                     continue;                 }                 left[i][j] = grid[i][j] == 'E' ? 1 : 0;                 if (j > 0) {                     left[i][j] += left[i][j - 1];                 }             }         }          //right,从右往左算         for (int i = 0; i < m; i++) {             for (int j = n - 1; j >= 0; j--) {                 if (grid[i][j] == 'W') {                     right[i][j] = 0;                     continue;                 }                 right[i][j] = grid[i][j] == 'E' ? 1 : 0;                 if (j < n - 1) {                     right[i][j] += right[i][j + 1];                 }             }         }          //结果填充dp         int res = Integer.MIN_VALUE;          for (int i = 0; i < m; i++) {             for (int j = 0; j < n; j++) {                 //只有在空地能放炸弹                 if (grid[i][j] == '0') {                     dp[i][j] = up[i][j] + down[i][j] + left[i][j] + right[i][j];                     if (dp[i][j] > res) {                         res = dp[i][j];                     }                 }             }         }         if (res != Integer.MIN_VALUE) {             return res;         } else {             return 0;         }     }


算法 动态规划

动态规划:博弈型博弈型dp一般从第一步分析,而不是最后一步,需要开n+1 1、LintCode 394 Coins in a Line【问题】有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币,直到没有硬币为止。拿到
2019-12-02 算法
动态规划:双序列型双序列型,就是有两个子序列/字符串,每个序列本身是一维的,可以转换为二维dp,序列型开数组开n+1,双序列型也是开n+1。 突破口:看串A和串B的最后一个字符是否匹配,是否需要串A/串B的最后一个字符,来缩减规模。 两种类
2019-12-02 算法

本文地址https://www.b2bchain.cn/?p=6031

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 算法-动态规划
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们