递归、分治

二分

贪心

DP

DP思想

  • DP-动态规划
  • DP解题思路
    • 确定状态:由于我们解决动态规划通常需要去开一个数组,既然是数组就需要明白其中的下标i啊j啊代表什么意思
      • 研究最优策略最后一步
      • 大问题拆分成小问题,小问题划分成小小问题…
    • 转移方程:DP解决问题的精髓就是这个,由不同的题不同考虑
    • 初始条件与边界条件:
      • 通常是a[0]啊a[1]的初值之类的
      • 数组不能越界,因为通常会在i和j上+-,很容易不小心就越界;
    • 计算顺序:记忆化之前我们运算所得到的结果。

DP-LeetCode相关

剑指Offer 63.股票的最大利润

image-20201007160636576

这种题很容易判断出来用DP写,为什么呢,因为只可能在左侧买,右侧卖,那就不用考虑万一右边有更小的买入值怎么办了。

换而言之,只需要一直考虑局部最优解,那么答案肯定是整体的最优解。

这题思路:

用一个min去不停更新数组的最小值,让当前遍历到的数字去减去这个值,就是利润,与之前所得到的最大值比大小,更新最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int maxProfit(int[] prices) {
//注意 这题不能让max = Integer.MIN_VALUE
//因为如果是这样的话 假如是从大到小排序的话 max值是负数,不符合题目要求,因为自作聪明,Error了一次
int max = 0;
int min = Integer.MAX_VALUE;
for(int i = 0 ; i < prices.length; i++) {
if(prices[i] <= min) {
//假如当前遍历到的值小于最小值,更新
min = prices[i];
//暂时跳出循环
continue;
}
//比较最大值,更新
max = Math.max(prices[i] - min, max);
}
return max;
}
}

70.爬楼梯

image-20201007184400404

这题太经典了,我写的第一道DP的题就是这个其实。

当时写到这个题就接触到了这种思想:

要爬上一层楼梯要几步?1步 对吧;两层楼梯呢?1+1步,ok,一次走两步 也ok

那走三层呢?三层其实就是两层基础上又多走一层呗,那就直接用上了两层的走法再加一层走法就好了;后续同理

所以这题最重要的就是设立子问题:走上n-1层有多少种解法,走上n-2层又有多少种解法,两个之和就是上n层可能的组合数

ps:我第一次解出来这个用的是迭代 那我顺便写一下迭代写法8

迭代解法代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int climbStairs(int n) {
if(n == 1)
return 1;
else if(n == 2)
return 2;
else {
int first = 1,second = 2,third = 0;
for(int i = 3;i <= n;i++){
third = first+second;
first = second;
second = third;
}
return second;
}
}
}

DP解法代码:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2 ; i <= n; i++) {
dp[i] = dp[i - 2] + dp[i - 1];
}
return dp[n];
}
}

5.最长回文子串

image-20201008142356074

这道题第一次纯暴力直接超时,后来想到了中心扩散的办法:枚举字符串各位置然后向两边扩散,但这方法感觉不具备一般性,于是虚心学习了DP的解法,这道题最优解法应该是线性的马拉车算法,但那个太难了且不具备一般性,我以后再学吧…

DP思路:

用一个二维数据dp[I] [j]来表示字符串i….j是否为回文字符串;

状态转移方程:dp[I] [j] = (s[i] == s[j]) && dp[i + 1] [j - 1]

什么意思呢?意思就算 i…j假如是回文串的话 等价于 首位字符相同且其中间部分也为回文字符串

边界条件:假如s[i] == s[j]且长度为2或者3 那么一定是回文字符串了 ;

DP代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public String longestPalindrome(String s) {
//特判1
if(s.length() == 0 || s == null) return "";
//特判2 假如是一个字符肯定是回文串
String ans = s.substring(0,1);
int len = s.length();
char[] a = s.toCharArray();
boolean[][]dp = new boolean[len][len];
for(int i = 0 ; i < len; i++) {
dp[i][i] = true;
}
//j用于遍历数组 i紧随其后
for(int j = 1 ; j < len; j++) {
for(int i = 0 ; i < j; i++) {
//如果不相等,则为false
if(a[i] != a[j]) {
dp[i][j] = false;
} else {
//j - i < 3是什么意思呢?
//其实是当s[i..j]长度为2或3的时候 假如头尾相等那么这段肯定是回文串了
if(j - i < 3) {
dp[i][j] = true;
//否则取决于中间是否为回文串
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
//假如首位相同 且 长度比之前的答案长度要长 则重新截取
if(dp[i][j] && j-i+1 > ans.length()){
ans = s.substring(i,j+1);
}
}
}
return ans;
}
}

322.零钱兑换

image-20201008203417632

这题和之前的爬楼梯有异曲同工之妙,为什么呢?

我们爬楼梯爬n层;这题需要凑够n的数值

我们爬楼梯有爬1层,2层;这题是用a元,b元,c元去凑;

ok,我们回到这题来,怎么解决呢?

  • 确定状态:假设有k枚硬币:a1,a2…ak凑成了目标amount 因此存在最后一枚硬币ak,那么前面的面值加起来=amount-ak

    没错吧?因此我们得到了原问题和子问题关系啦:最少用多少枚硬币拼成amount最少用多少枚硬币拼成amount-ak

  • 转移方程

    i 为 最少用多少枚硬币拼成 i coin 为 我们可利用的硬币面值

    1
    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
  • 初始条件与边界

    • 边界:i - coin < 0 意思是不存在能凑成差值的方法,定义为正无穷
    • 初始条件:基准值,就是不能算出来的值,需要用到这个去推理得到其他的结果的值:dp[0] = 0 为什么呢 不需要硬币肯定是0
  • 计算顺序:到底是应该直接从最大面值开始还是最小面值开始呢?

    为了算dp[x] 我们需要用到dp[x - 1]..d[x - 2] 因此是正序遍历

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public int coinChange(int[] coins, int amount) {
//特判1
if(amount == 0) return 0;
//特判2
if(coins.length == 0) return -1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, 1, dp.length, Integer.MAX_VALUE);
//迭代器遍历 直接取出数组每个数值 外层for循环所有选择的最小值
for (int coin : coins) {
//判断差值
for(int i = coin ; i <= amount; i++) {
//假如存在可以凑成差值的组合的话
if(dp[i - coin] != Integer.MAX_VALUE) {
//状态转移 在已经有的组合 和 拼出i - coin枚硬币数+自己的一枚中选择一个少的
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
//假如有解的话 输出
if(dp[amount] != Integer.MAX_VALUE) {
return dp[amount];
}
return -1;
}
}

面试题08.11. 硬币

image-20201008212810143

为什么把这题放在零钱兑换下面呢 其实这两题大致相同,只不过一个是要在所有组合数中选择硬币数最小的;

而这题是统计所有的组合数

同样的方法:

  • 确定状态:dp[n]为组成总面额为n的情况数

  • 转移方程

    1
    dp[i] = (dp[i] + dp[i - coin]) % 1000000007;
  • 初始条件与边界:dp[0] = 1 组成0的方法有1种,就是什么都不放,同时这也是边界限制条件 若 i - coin = 0 也就是面值正好时,可以只放一个硬币了 也就是1

  • 计算顺序:同样是正序遍历

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int waysToChange(int n) {
int[] coins = new int[]{1, 5, 10, 25};
if(n == 0) return 0;
int[] dp = new int[n + 1];
dp[0] = 1;
for (int coin : coins) {
for(int i = coin; i <= n; i++) {
dp[i] = (dp[i] + dp[i - coin]) % 1000000007;
}
}
return dp[n];
}
}

排序