菲波那切数列

L70 爬楼梯

easy 过。 子问题不是独立的，还包含了子子问题。

L198 大家劫舍(☆)

描述问题的最优子结构(一个问题的最优解包含了子问题的一个最优解)，递归定义最优解的值。

最优子结构性质是能应用动态规划的标志之一。

注: easy 过

L213 打家劫舍 II(☆☆)

也称环形抢劫，首先考虑减小问题的规模，后面发现可以转化为L198. 分别对区间0n-2 和 1n-1用L198的代码，最大值即为所求。

2021-1-10 ： 要用到组合的思路，分类去列情况。不要光想。

L337. 打家劫舍 III(☆☆☆☆)

树形dp问题. 用到了后序遍历

f(o)表示选择o结点情况下,所得到的最大和，g(o)表示不选择o结点情况下,所得到的最大和

☆//每个结点有3次访问机会，用后序遍历可以将递归转化为非递归

☆树形dp问题这里的表用的是hashmap

2021-1-10 22:06:22

g = max {f(l), f(l)} + max{f(r),g(r)}

为什么要用hash？

• 映射，键值对。存储节点的f g值 ，所以用2个hashmap.

为什么要用后序？

• 用后序递归就可以

• 因为递归是从上到下，动态规划要自底向上，而最后遍历到根的正是后序。

• 问题的规模很小达到可解时。

  • f
    • 最后肯定能遍历到叶子节点，叶子节点的f就是自身的val
    • 非叶子节点的f，g(l) + g(r)
  • g
    • 叶子节点的g就是0 , 用getOrDefault，从hashmap中取 默认是0.，因为非递归会从最底节点开始。

矩阵路径

• 1. 矩阵的最小路径和
  • easy 过 减小规模 + 写出递归 + 自底向上. 但是写的不仔细 ，是快造成的
• 2. 矩阵的总路径数
  • easy 过

L416 分割等和子集

累加和问题,这题递归方法超时。

2020-09-22 23:15:18当前的动态规划解法有待进一步超时

动态规划步骤：

考虑减小问题的规模

尝试写出递推式=>写出递归的解法

用空间换时间，转为动态规划。

L53 最大子序和

这题关键在于定义最优解，用 f(i) 代表以第 i个数结尾的「连续子数组的最大和」，找出最大的。 a(i) 表示数字第i个元素，要判断是否要加入前面的子序和。前面的大于0才加。

L121121. 买卖股票的最佳时机

f(i)定义为数组前i个数的解，就是第i天的解，可能为负数，不是最优解。也就是找出每天的解，用1个max变量来记录最优解. 第i天的解第i天 - 前面最小的。

这个解法在暴力解(问题的所有子问题) 和纯动态规划之间.

序列

L300. 最长递增子序列(☆☆☆☆)

• 关键在于定义f(n) ：以n结尾的最长递增子序列的长度 , f(n-1)就是以第n-1个数结尾的最长递增子序列的长度。前面的每个f(i) i,从 0到N-1 , 于第n个数比较，
• 下一步减小问题规模没错，f(n) 于f(n-1)比较
• 然后自底向上

子串，子数组一定连续，子序列不一定连续。

L376 摆动序列

• 有和最长递增子序列类似的地方,这题要求正负交替的子序列
• 第一个差可能是正可能是负 这点没注意到 ， 因此我的解法分了2种情况

L646最长数对链

• 数对的第一个数是无序，因此我先写了选择排序
• f[i] 表示以第i个数对结尾的 最长数对链的长度

L1143 最长公共子序列

重要的写出的递归式。 找f(n) 和f(n-1)的关系，这里是先假设x和y的最后一个字母是否相同，反过来考虑，也是从上到下，很关键。

• 定义要的那个表的d[i][j]的定义 很重要

累加和问题：

• L416
• 累加和等于target(2^n^种)

数组区间

L303 过

背包问题

416. 分割等和子集

*** 再做不会做了，挺有难度。

什么叫多项式时间复杂度？

动态规划解法：

题目可以转换为能否找到几个数的和等于数组和的一半target。

传统的「0-10−1 背包问题」要求选取的物品的重量之和不能超过背包的总容量。

异常情况：

0.n < 2 不能被划分

1.和为奇数->false

2.最大的数比target大，那么除了最大的数的其他数的和小于target

关键是定义dp[i][j] 表示在范围[0,i]内能否找个几个数的和等于j ,分为j >= nums[i] 和 j < nums[i]。

i从[0,n-1] , j从 0 ,target.

1.j >= nums[i]

• dp[i][j] = dp[i-1][j] | dp[i - 1][j - nums[i]];
  • 分为选Nums[i] 和不选的情况 只要满足其一就行

2.j < nums[i]

• dp[i][j] = dp[i-1][j] 不能选

322. 零钱兑换

花了蛮长时间。 没定义好dp数组，他就是一维的。 没找到递推关系。

f[amout] = f[amout - c] + 1 . 思维一直在 二维dp

518. 零钱兑换 II

在LeetCode上有两道题目非常类似，分别是

• 70.爬楼梯

• 518.零钱兑换 II

如果我们把每次可走步数/零钱面额限制为[1,2], 把楼梯高度/总金额限制为3. 那么这两道题目就可以抽象成”给定[1,2], 求组合成3的组合数和排列数”。

494 改变一组数的正负号使得它们的和为一给定数

目标和

背包问题，范围是在-1000，1000.

关键在定义dp[i][j]的含义 以及它的表示。

474 01 字符构成最多的字符串

这个太难。

2