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

算法-动态规划

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

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

算法 动态规划

算法

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

动态规划:划分型

划分型动态规划就是给定长度为N的字符串,需要划分成若干段,段数不限,每一段满足一定的性质。在学校oj中做过的书本分发、漆狗屋这种就属于划分型。开数组也是开n+1

1、Lintcode 512 解码方法

【问题】有一个消息包含A-Z通过以下规则编码:’A’ -> 1,’B’ -> 2…’Z’ -> 26,现在给你一个加密过后的消息,问有几种解码的方式。

输入: "12" 输出: 2 解释: 它可以被解码为 AB (1 2) 或 L (12).

【分析】从最后一步出发,最后一个或两个数字对应一个字母。给定字符串长度为N,需要球它的解密方式有多少种,那就需要知道前N-1个数字有多少种解密方式,以及前N-2个数字有多少种解密方式,这就是子问题。

【状态转移方程】dp[i] = dp[i-1] + dp[i-2] (最后两个字母范围为10~26)

public static int numDecodings(String s) {         char[] chs = s.toCharArray();         int n = chs.length;         if (n == 0) {             return 0;         }         int[] dp = new int[n + 1];         dp[0] = 1;  //空串也算一种         for (int i = 1; i <= n; i++) {             //一位数必须要在1~9,0是不算的             if (chs[i - 1] != '0') {                 dp[i] += dp[i - 1];             }             if (i >= 2) {                 int num = (chs[i - 2] - '0') * 10 + (chs[i - 1] - '0');                 if (num >= 10 && num <= 26) {                     dp[i] += dp[i - 2];                 }             }         }         return dp[n];     }

2、Lintcode 513 Perfect Squares

【问题】给一个正整数 n, 请问最少多少个完全平方数(比如1, 4, 9…)的和等于n。

【分析】重点关注最后一个完全平方数 j^2^,n – j^2^ 也是被分成最少的完全平方数之和,这就是子问题

  • dp[i]就代表i最少被分成几个完全平方数之和,dp[i] = min{dp[i - j^2]+1}
public int numSquares(int n) {         int[] dp = new int[n + 1];         dp[0] = 0;         for (int i = 1; i <= n; i++) {             dp[i] = Integer.MAX_VALUE;             //j必须从1开始,如果不从1开始,dp[i],dp[i]+1会越界             for (int j = 1; j * j <= i; j++) {                 dp[i] = Math.min(dp[i], dp[i - j * j] + 1);             }         }         return dp[n];     }

3、Lintcode 108 Palindrome Partitioning II

【问题】给定字符串 s, 需要将它分割成一些子串, 使得每个子串都是回文串,最少需要分割几次?

【分析】从最后一步出发,假设最后一段回文串为s[j…n-1],需要知道s中前j个字符[0…j-1]最少可以划分成多少个回文串,这就是子问题。

  • dp[i] = min{dp[j]} + 1(0 <= j < i && s[j…i-1]为回文串的情况下)
  • 初始条件:空串可以被划分为0个回文串

下面这么写,超时

public int minCut(String s) {         int n = s.length();         if (n == 0) {             return 0;         }         int[] dp = new int[n + 1];         dp[0] = 0;          for (int i = 1; i <= n; i++) {             dp[i] = Integer.MAX_VALUE;             for (int j = 0; j < i; j++) {                 //如果最后一段是回文串                 if (isPalindrome(s.substring(j, i))) {                     dp[i] = Math.min(dp[i], dp[j] + 1);                 }             }         }         //问的是切几刀,刀数 = 段数 - 1,比如aab,分两段,切1刀         return dp[n] - 1;     }      public boolean isPalindrome(String s) {         return new StringBuilder(s).reverse().toString().equals(s);     }

需要把所有的回文串保存在二维数组中,这样不用每次再去判断是否为回文串

时间复杂度O(N^2^),空间复杂度O(N^2^)

public int minCut(String s) {         char[] chs = s.toCharArray();         int n = chs.length;         if (n == 0) {             return 0;         }          boolean[][] isPalindrome = calcPalindrome(chs);   //判断是否为回文串         int[] dp = new int[n + 1];         dp[0] = 0;  //前0个回文串分割0个          for (int i = 1; i <= n; i++) {             dp[i] = Integer.MAX_VALUE;             for (int j = 0; j < i; j++) {                 //如果j到i-1是回文串,就更新                 if (isPalindrome[j][i - 1]) {                     dp[i] = Math.min(dp[i], dp[j] + 1);                 }              }         }         //aab,分成两段回文串只要切一刀,段数 - 1         return dp[n] - 1;     }      //利用二维数组,不用每次去判断是不是回文串     public boolean[][] calcPalindrome(char[] chs) {         int n = chs.length;         boolean[][] f = new boolean[n][n];          //初始化         for (int i = 0; i < n; i++) {             for (int j = i; j < n; j++) {       //从i到j是否为回文串,所以j是从i开始                 f[i][j] = false;             }         }         //生成回文串的过程,如果回文串长度是奇数,那就是由中心点向两边生成,如果回文串长度是偶数,那就是由中心线向两边生成         //奇数的情况,c为中心center,共n个中心点         for (int c = 0; c < n; c++) {             int i = c, j = c;             while (i >= 0 && j < n && chs[i] == chs[j]) {                 f[i][j] = true;                 i--;                 j++;             }         }         //偶数的情况,共n-1条中心线         for (int c = 0; c < n; c++) {             int i = c, j = c + 1;             while (i >= 0 && j < n && chs[i] == chs[j]) {                 f[i][j] = true;                 i--;                 j++;             }         }         return f;     }

4、LintCode 437 Copy Books

书本分发、漆狗屋这类题,在学校OJ做烂掉了。这个题也能二分法做。

【问题】给定 n 本书, 第 i 本书的页数为 pages[i]。 现在有 k 个人来复印这些书籍,,而每个人只能复印编号连续的一段的书, 比如一个人可以复印 pages[0], pages[1], pages[2], 但是不可以只复印 pages[0], pages[2], pages[3]而不复印 pages[1]。所有人复印的速度是一样的,,复印一页需要花费一分钟, 并且所有人同时开始复印. 怎样分配这 k 个人的任务, 使得这 n 本书能够被尽快复印完?返回完成复印任务最少需要的分钟数。

【分析】当有i个抄写员的时候,一共n本书,从最后一步出发,第i个抄写员抄几本书,可能是0~n本,假设第i个抄写员抄写j本,前i-1个抄写员一共抄写n-j本书。前i-1个抄写员抄写完耗时T1,第i个抄写员抄写完耗时T2,i个人抄完n本书,花费的时间是max(T1,T2),我们要求所有分配情况下,抄完书的最小时间花费。

![

//k个抄写员     private static int solve(int[] nums, int k) {         int n = nums.length;    //一共几本书         if (n == 0) {             return 0;         }         int[][] dp = new int[k + 1][n + 1];         //初始化:k个抄写员抄写0本书,花费时间都是0         for (int i = 0; i <= k; i++) {             dp[i][0] = 0;         }         //初始化:0个抄写员抄写0本书,花费时间是0,0个抄写员抄写1本、2本。。。花费时间无穷大         for (int i = 1; i <= n; i++) {             dp[0][i] = Integer.MAX_VALUE;         }          //一共前i个抄写员         for (int i = 1; i <= k; i++) {             //前i个抄写员一共抄写j本书             for (int j = 1; j <= n; j++) {                 dp[i][j] = Integer.MAX_VALUE;                 int sum = 0;                 //前i-1个抄写员抄写l本书,l从j开始,也就是先让最后一个人从0本开始,然后累加,这样就不用额外去计算这个人抄写花费的时间                 for (int l = j; l >= 0; l--) {                     dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][l], sum));                     if (l > 0) {                         sum += nums[l-1];                     }                 }             }         }         return dp[k][n];     }

二分法,二分可能的答案。每次判断什么呢?判断k个人能不能在这个时间(mid)里搞定

    //二分,时间复杂度O(nlogm), n:书本数目, m:总页数。     public static int copyBooks(int[] pages, int k) {         // 假设的做二分查找的区间是 0 ~ max         int start = 0, end = 0; //end为所有书都由一个人抄         for (int i = 0; i < pages.length; i++) {             end += pages[i];         }          //log page,N本书for检查一遍,O(n)         while (start + 1 < end) {             int mid = start + (end - start) / 2;             //如果k个人能在mid时间内搞定,说明我们可以继续 【缩短】 时间,而不是提高时间!!!             if (check(pages, mid, k)) {                 end = mid;             } else {                 start = mid;             }         }         //double check start         if (check(pages, start, k)) {             return start;         } else {             return end;         }     }      private static boolean check(int[] pages, int limit, int k) {         int num = 1;    //所需人数         int count = 0;  //每个人工作了多久         for (int page : pages) {             if (page > limit) {     //一定要判断一下!!!                 return false;             }             if (count + page > limit) {                 num++;                 count = 0;             }             count += page;         }         return num <= k;     }


算法 动态规划

动态规划:背包型数组开n+1,背包关键就是看最后一步。 1、01背包–求maxLintCode 92: Backpack 【问题】在n个物品中挑选若干物品装入背包,最多能装多满?假设背包的大小为m,每个物品的大小为A[i] 【分析】从最后一
2019-12-02 算法
动态规划:博弈型博弈型dp一般从第一步分析,而不是最后一步,需要开n+1 1、LintCode 394 Coins in a Line【问题】有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币,直到没有硬币为止。拿到
2019-12-02 算法

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

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

评论 抢沙发

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

b2b链

联系我们联系我们