小猪学算法-动态规划

本文简述动态规划的思想及常见经典面试题：

动态规划（Dynamic Programming）简称DP，是一般算法中最灵活多变的一种。因为其只是一种思想，但实现方式有很多种，基于特定的实现方式各整出五花八门的题目。

但核心思想就几句话：

  • 找状态转移方程
  • 问题具有最优子结构
  • 重叠子问题

其中最灵活多变的就是要找出合适的状态转移方程了。其中还要注意的是dp数组的定义，因为数组的定义决定了状态转移方程的定义，小猪亲自试了力扣上面的很多动态规划的题目，在没有熟悉其固定套路之前确实很难想到对应的解法。

只有多多联系，多多思考总结讨论，才能在遇到类似题目时手到擒来，相信读者们一定可以。

1、线性 DP

最经典单串：

  1. 最长上升子序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int lengthOfLIS(int[] nums) {
    int length = nums.length;
    int[] dp = new int[length];
    int ans = 0;
    for(int i =0; i<length; i++){

        for(int j = 0; j<i; j++){
            if(nums[j]<nums[i]){
                dp[i] = Math.max(dp[j]+1, dp[i]);
            }
        }
        ans = Math.max(ans, dp[i]);

    }
    return ans+1;
}

最经典双串：

  1. 最长公共子序列

经典问题：

  1. 三角形最小路径和

  2. 最大子序和

  3. 乘积最大子数组

  4. 鸡蛋掉落（DP+二分）

  5. 俄罗斯套娃信封问题

打家劫舍系列: (打家劫舍3 是树形DP)

  1. 打家劫舍

  2. 打家劫舍 II

股票系列:

  1. 买卖股票的最佳时机

  2. 买卖股票的最佳时机 II

  3. 买卖股票的最佳时机 III

  4. 买卖股票的最佳时机 IV

  5. 最佳买卖股票时机含冷冻期

  6. 买卖股票的最佳时机含手续费

字符串匹配系列

  1. 编辑距离

  2. 通配符匹配

  3. 正则表达式匹配

2、区间 DP

  1. 最长回文子序列

  2. 统计不同回文子字符串

  3. 多边形三角剖分的最低得分

  4. 奇怪的打印机

  5. 戳气球

3、背包 DP

  1. 分割等和子集 (01背包-要求恰好取到背包容量)

  2. 目标和 (01背包-求方案数)

  3. 零钱兑换 (完全背包)

  4. 零钱兑换 II (完全背包-求方案数)

  5. 一和零 (二维费用背包)

4、树形 DP

  1. 二叉树中的最大路径和

  2. 树的直径 (邻接表上的树形DP)

  3. 二叉树的直径

  4. 最大 BST 子树

  5. 打家劫舍 III

5、状态压缩 DP

  1. 我能赢吗

  2. 优美的排列

  3. 骑士拨号器

  4. 参加考试的最大学生数

6、数位 DP

  1. 数字 1 的个数

  2. 最大为 N 的数字组合

  3. 可被 K 整除的最小整数

7、计数型 DP

计数型DP都可以以组合数学的方法写出组合数，然后dp求组合数

  1. 不同路径

  2. 不同路径 II

  3. 不同的二叉搜索树 (卡特兰数)

  4. 不相交的握手 (卢卡斯定理求大组合数模质数)

8、递推型 DP

所有线性递推关系都可以用矩阵快速幂做，可以O(logN)，最典型是斐波那契数列

  1. 爬楼梯

  2. 斐波那契数

  3. 骑士拨号器

  4. N 天后的牢房

  5. 第 N 个泰波那契数

9、概率型 DP

求概率，求数学期望

  1. 分汤

  2. 新21点

10、博弈型 DP

策梅洛定理，SG 定理，minimax

翻转游戏

  1. 翻转游戏

  2. 翻转游戏 II

Nim游戏

  1. Nim 游戏

石子游戏

  1. 石子游戏

  2. 石子游戏 II

井字游戏

  1. 判定井字棋胜负

  2. 有效的井字游戏

  3. 找出井字棋的获胜者

11、记忆化搜索

本质是 dfs + 记忆化，用在状态的转移方向不确定的情况

  1. 矩阵中的最长递增路径

  2. 出界的路径数

赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

"我是小猪.2012年硕士毕业后一直从事软件开发工作,先后从事互联网应用开发,IOT平台开发,目前在上海从事医疗大数据行业. <br><br>\n 这个站点作为个人站点,不定期更新自己的一些技术笔记,技术教程,生活感悟. <br><br>\n 茫茫互联网,我不会主动在任何社区推广本站,如果缘分至此,有幸得到您的拜访,何不为这份缘分留下一些印记."