【剑指offer2】 chap14 动态规划

分冶：

• 无重叠，直接递归

• 有重叠 ，建立 dp表

剑指 Offer II 088. 爬楼梯的最少成本

• 两种空间优化方案

• 剑指 Offer II 089. 房屋偷盗

• 剑指 Offer II 090. 环形房屋偷盗

  • 分两种情况，借助helper

  • d[p]

• 剑指 Offer II 091. 粉刷房子

  • 256. 粉刷房子

  • 265. 粉刷房子 II

  • 276. 栅栏涂色

  • 不含连续1的非负整数

  • 656. 金币路径

    • 从最后一个位置回退

    • 0<= i <=length-2

    • dp[i] = min(A[i] + dp[j])   i+1<=j<=min(i+B,length)   && A[j] >=0

    • next[i] = j of min_cost

    • 输出路径

      • 0<=i0——i+1

      • i == lenth -1 && coins[i] >= 0——length

      • else——null

  • 152. 乘积最大子数组

    • maxP[i] = max  (cur*maxP[i-1],   cur*minP[i-1],  cur)

    • minP[i] = min  (cur*maxP[i-1], cur*minP[i-1], cur)

    • 53. 最大子数组和      （线段树）

      • dp  O(n)

      • 前缀和

      • 分冶 

    • 740. 删除并获得点数

    • 978. 最长湍流子数组

    • 697. 数组的度

    • 股票问题系列通解（转载翻译）

    • https://labuladong.github.io/algo/3/26/96/

      • base case：

        • dp[-1][...][0] = dp[...][0][0] = 0

        • dp[-1][...][1] = dp[...][0][1] = -infinity

      • 状态转移方程：

        • dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])

        • dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

• 剑指 Offer II 092. 翻转字符    （双序列递推）

  • 末尾为0

  • 末尾为1

• 剑指 Offer II 093. 最长斐波那契数列

• 剑指 Offer II 094. 最少回文分割

int len = s.length();
//isPalindrome
boolean[][] isPal = new boolean[len][len];

for(int i = 0; i < len; i++){
    for(int j = 0; j <= i; j++){
        if(s.charAt(i) == s.charAt(j) && (i <= j + 1 || isPal[j+1][i-1])){
            isPal[j][i] = true;
        }
    }
}

• 剑指 Offer II 095. 最长公共子序列

if(text1.charAt(i-1) == text2.charAt(j-1)){
    dp[i][j] = dp[i-1][j-1]+1;
}else{
    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}

• • 583. 两个字符串的删除操作  （转化一下）

return len1 + len2 - 2 * dp[len1][len2];

• • 712. 两个字符串的最小ASCII删除和

    • 注意 0 和另一字符串的 初始化    其他结构类似

• 剑指 Offer II 096. 字符串交织

  • 注意行列边界初始化

dp[i + 1][j + 1] = (ch1 == ch3 && dp[i][j + 1]) || (ch2 == ch3 && dp[i + 1][j]);

• 剑指 Offer II 097. 子序列的数目

路径数量

路径的最大值，最小值

障碍物问题

剑指 Offer II 098. 路径的数目  无障碍物，求路径数

两种写法：二维数组，一维数组

63. 不同路径 II  (障碍物，求路径数)

两种写法：二维数组，一维数组

剑指 Offer II 099. 最小路径之和（无障碍物）

两种写法：二维数组，一维数组

174. 地下城游戏（障碍物，路径和）

剑指 Offer II 100. 三角形中最小路径之和

问题特点

• 信息：一组物品，物品重量，物品价格

• 限定：总重量

• 目标：总价格最高

问题细分：

• 0-1背包问题：每种物品只有一个

• 有界背包问题：每种物品有多个

• 无限背包问题：每种物品有无穷多个

力扣

剑指 Offer II 101. 分割等和子集

剑指 Offer II 102. 加减的目标值

剑指 Offer II 103. 最少的硬币数目

剑指 Offer II 104. 排列的数目

377. 组合总和 Ⅳ