Leetcode / dp

记录前边问题结果，利用递推公式求解，空间换时间。

一维数组dp

509 斐波那契数 / 70. 爬楼梯 / 矩形覆盖
338 比特位计数(dp + 位运算)
55 跳跃游戏
45 跳跃游戏 II（dp/贪心）
198 打家劫舍
213 打家劫舍 II
121 最佳买卖股票时机 (一次买卖)
122 买卖股票的最佳时机 II (多次买卖)
264/剑指49 丑数【数学】
650 只有两个键的键盘

对每一个格子 i（i个A），如果i可以被j除尽，说明 j 个A可以通过复制粘贴得到 i 个A，复制粘贴次数为 i / j

子序列与子串

子序列：子序列不要求元素连续。

300 最长递增子序列
516 最长回文子序列
1143/剑指95 最长公共子序列

子串：要求数组元素必须连续

53/剑指42 连续子数组的最大和 (子串最大和)
674 最长递增子串
5 最长回文子串
最长公共子串

二维数组dp

62 不同路径
63 不同路径 II
剑指47 礼物的最大价值(最大路径和) / 64 最小路径和
120 三角形最小路径和
920 播放列表的数量

dp背包

给定一个背包容量 target，一个数组 nums(物品)，能否按一定方式选取 nums 中的元素得到target。背包容量 target 和物品 nums 的类型可能是数，也可能是字符串
target可能题目已经给出(显式)，也可能需要从题目的信息中挖掘出来(非显式)(常见的非显式 target 比如sum/2 等)
选取方式有常见的以下几种：每个元素选一次/每个元素选多次/选元素进行排列组合
1、0/1背包：每个元素最多选取一次, 外循环 nums,内循环 target, target 倒序且 target>=nums[i];
2、完全背包：每个元素可以重复选择, 外循环 nums,内循环 target, target 正序且 target>=nums[i];
3、组合背包：背包中的物品要考虑顺序, 外循环target,内循环 nums, target 正序且 target>=nums[i];
4、分组背包：不止一个背包，需要遍历每个背包, 三重循环：外循环背包bags,内部两层循环根据题目的要求转化为1,2,3三种背包类型的模板

而每个背包问题要求的也是不同的，按照所求问题分类，又可以分为以下几种：
1、最值：要求最大值/最小值

1	dp[i] = max/min(dp[i], dp[i-nums]+1)或dp[i] = max/min(dp[i], dp[i-num]+nums);

2、存在：是否存在…，满足…

1 2	// boolean dp[i]=dp[i]\|\|dp[i-num];

3、组合：求所有满足……的排列组合

1	dp[i]+=dp[i-num];

// 二维dp背包，自底向上
public int knapsack_bottom_up(int[] weights,int[] values, int capacity){
    int n = weights.length;
    // dp[i][w]: 对于第i个物品，总重不超过x的最大价值
    int[][] dp = new int[n][capicity];
    for(int i = 0; i < n; i++) dp[i][0] = 0;
    for(int j = 0; j < capacity; j++) dp[0][j] = 0;
    for(int x = 1; x < n; x++){
        for(int y = 1; y < capacity; y++){
            int w = weights[x];
            int v = values[x];
            if(y < w) dp[x][y] = dp[x-1][y]; // 第i个物品的重量w超出限制y
            else dp[x][y] = Math.max(dp[x-1][y], dp[x-1][y-w]+v);
        }
    }
    return dp[n-1][capacity-1];
}

698 划分为k个相等的子集 - 回溯+剪枝
473 火柴拼正方形（划分为4个相等的子集） - 回溯+剪枝
416 分割等和子集（划分为2个相等的子集） - dp背包

单调栈

一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置

739 每日温度

图

图的表示：邻接表 graph[i]: 第i个点的相邻节点

785 判断二分图（dfs点染色）

我们任选一个节点开始，将其染成红色，并从该节点开始对整个无向图进行遍历；
在遍历的过程中，如果我们通过节点 u 遍历到了节点 v（即 u 和 v 在图中有一条边直接相连），那么会有两种情况：
如果 v 未被染色，那么我们将其染成与 uu 不同的颜色，并对 v 直接相连的节点进行遍历；
如果 v 被染色，并且颜色与 uu 相同，那么说明给定的无向图不是二分图。我们可以直接退出遍历并返回 false 作为答案。
当遍历结束时，说明给定的无向图是二分图，返回 true 作为答案。