动态规划 入门

什么是动态规划

动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。

《算法图解》的定义是:“动态规划先解决子问题,再逐步解决大问题”

背包问题

假设你是一个贪婪的小偷,背着可装35磅物品的背包,在商场伺机偷取物品,你可盗窃的物品有下面三种:

物品 价格 重量
音响 3000美元 30磅
笔记本电脑 2000美元 20磅
吉他 1500美元 15磅

简单算法

最简单的算法是:枚举出所有可能的组合,从中找出价值最高的组合 这样可行,但速度非常慢。在仅有三件商品的情况下,需要计算8个不同的集合;有四件商品需要计算16个集合。每增加一件商品,需要计算的集合数都将翻倍!这种算法的运行时间为

$$ O(a^n) $$

动态规划

动态规划的核心思想就是拆分子问题,记住过往,减少重复计算。 并且动态规划一般都是自底向上的。 《算法图解》并没有讲清楚何为动态规划,以及其实现,我将结合这篇博客来讲解 总的来说有四步:

  • 穷举分析
  • 确定边界
  • 找出规律,确定最优子结构
  • 写出状态转移方程

什么是最优子结构?有这么一个解释:

一道动态规划问题,其实就是一个递推问题。假设当前决策结果是f(n),则最优子结构就是要让 f(n-k) 最优,最优子结构性质就是能让转移到n的状态是最优的,并且与后面的决策没有关系,即让后面的决策安心地使用前面的局部最优解的一种性质

1. 穷举分析 背包可放35磅 放15磅

物品\重量 15
吉他 15磅 1500
笔记本电脑 20磅 1500
音响 30磅 1500

放20磅

物品\背包价值\重量 15 20
吉他 15磅 1500美元 1500 1500
笔记本电脑 20磅 2000美元 1500 2000
音响 30磅 3000美元 1500 2000

放35磅

物品\背包价值\重量 15 20 35
吉他 15磅 1500美元 1500 1500 1500
笔记本电脑 20磅 2000美元 1500 2000 3500
音响 30磅 3000美元 1500 2000 3500

不难看出: 1.如果放不下当前行的物品,则直接从上方单元格抄下价格 2.如果放得下,判断本行与上方的价值,填入最高价值

2.确定边界 边界情形为第一行,即最轻的物品需要填入,以保证下方单元格能获取到价格

3.确定最优子结构 当前单元格 = Max(上方单元格价值, 本行物品加入后的价值)

将第 i 件物品的价值 W[i] 加上 向容量为v-C[i] 的背包装入前 i-1 件物品 (现有容量v - 当前物品大小C[i]) 这个 子问题 的最大价值 F[i-1][v-C[i]] (先把第 i 件物品加入背包,然后考虑安排剩余的空间容量)

4.状态转移方程 f[i][j] = Max( f[i - 1][j] , f[i-1][v-C[i]])

leetcode例题

5.最长回文子串 给你一个字符串 s,找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:

输入:s = "cbbd"
输出:"bb"

提示: 1 <= s.length <= 1000 s 仅由数字和英文字母组成

代码实现:

public static String longestPalindrome(String s) {
        int len = s.length();
        if (len == 1) {
            return s;
        }
        int rsLen = 1;
        int start = 0;
        // 创建表格
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] arr = s.toCharArray();

        /*
        初始化后的示例
        	0	1	2	3	4	right
        0	T	F	F	F	F
        1	F	T	F	F	F
        2	F	F	T	F	F
        3	F	F	F	T	F
        4	F	F	F	F	T
        left
        
        对角线 单字符是回文串
        */
//        先按 右指针(列) 遍历
        for (int right = 1; right < len; right++) {
//            再按行遍历
//            只需判断对角线上部,即 left < right
            for (int left = 0; left < right; left++) {
//                判断两端字符相等
                if (arr[left] == arr[right]) {
//                    边界情形  字符串长度小于3的情况
                    if (right - left < 3) {
                        dp[left][right] = true;
                    } else {
//                        普通情况,两头的字符相等的话,找 left + 1, right - 1
//                        即指针都向中间移一格,如果中间的是回文,那当前也是回文
                        dp[left][right] = dp[left + 1][right - 1];
                    }
                }
//                如果当前是回文,且当前字符串长度大于最大字符串长度
                if (dp[left][right] && right - left + 1 > rsLen) {
                    start = left;
//                    最大字符串长度
//                    如果直接取右指针会遇到奇偶问题
                    rsLen = right - left + 1;
                }
            }
        }
        return s.substring(start, start + rsLen);
    }

参考: 1.《算法图解》人民邮电出版社 2. 看一遍就理解:动态规划详解

ねぇ,あなたは何色になりたい