欢迎关注个人公众号：爱喝可可牛奶LeetCode算法训练-动态规划理论知识动态规划当前状态是由前一个状态推导出来的，而贪心没有状态的转移动态规划需要借助dp数组，可能是一维也可能是二维的首先要明确dp数组是用来干什么的，下标对应什么状态如何转移？也就是理清递推公式dp数组如何初始化如何遍历举个栗子模拟推导一遍LeetCode509.斐波那契数分析F(n)=F(n-1)+F(n-2)，其中n>1代码classSolution{publicintfib(intn){if(nLeetCode70.爬楼梯分析错误没有理清递推函数classSolution{publicintclimbStairs(in
题目传送门：https://www.luogu.com.cn/problem/P1073思路：首先，我们目的是想要在图上dp求最优的路线，但是原图上会存在环，那么我们就要先通过tarjan缩点，将所有环缩成一个点，同时，记录每个点的最大值和最小值，缩点得到DAG后，我们可以在DAG上进行dp，每次转移有三种方式，一是保留上一个点的dp值，二是求得目前所在点的值，三是这个点本身的dp值，三者取最大就ok了。还要注意的是，在建DAG图的时候，要记录每个点的入度，在之后的dp过程中，每一个点在全部走到的时候，才能压入队列，进行更新操作，保证dp内的值是最优的，也就是无后效性。代码：1#include
题目传送门：https://www.luogu.com.cn/problem/P1073思路：首先，我们目的是想要在图上dp求最优的路线，但是原图上会存在环，那么我们就要先通过tarjan缩点，将所有环缩成一个点，同时，记录每个点的最大值和最小值，缩点得到DAG后，我们可以在DAG上进行dp，每次转移有三种方式，一是保留上一个点的dp值，二是求得目前所在点的值，三是这个点本身的dp值，三者取最大就ok了。还要注意的是，在建DAG图的时候，要记录每个点的入度，在之后的dp过程中，每一个点在全部走到的时候，才能压入队列，进行更新操作，保证dp内的值是最优的，也就是无后效性。代码：1#include
一、题目大意标签:动态规划https://leetcode.cn/problems/01-matrix给定一个由0和1组成的矩阵mat ，请输出一个大小相同的矩阵，其中每一个格子是mat中对应位置元素到最近的0的距离。两个相邻元素间的距离为1。示例1：输入：mat=[[0,0,0],[0,1,0],[0,0,0]]输出：[[0,0,0],[0,1,0],[0,0,0]]示例2：输入：mat=[[0,0,0],[0,1,0],[1,1,1]]输出：[[0,0,0],[0,1,0],[1,2,1]]提示：m==mat.lengthn==mat[i].length11mat[i][j]iseithe
一、题目大意标签:动态规划https://leetcode.cn/problems/minimum-path-sum给定一个包含非负整数的m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。示例1：输入：grid=[[1,3,1],[1,5,1],[4,2,1]]输出：7解释：因为路径1→3→1→1→1的总和最小。示例2：输入：grid=[[1,2,3],[4,5,6]]输出：12提示：m==grid.lengthn==grid[i].length10二、解题思路二维的动态规则，定义一个二维dp数组，其中dp[i][j]
一、题目大意标签:动态规划https://leetcode.cn/problems/01-matrix给定一个由0和1组成的矩阵mat ，请输出一个大小相同的矩阵，其中每一个格子是mat中对应位置元素到最近的0的距离。两个相邻元素间的距离为1。示例1：输入：mat=[[0,0,0],[0,1,0],[0,0,0]]输出：[[0,0,0],[0,1,0],[0,0,0]]示例2：输入：mat=[[0,0,0],[0,1,0],[1,1,1]]输出：[[0,0,0],[0,1,0],[1,2,1]]提示：m==mat.lengthn==mat[i].length11mat[i][j]iseithe
一、题目大意标签:动态规划https://leetcode.cn/problems/minimum-path-sum给定一个包含非负整数的m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。示例1：输入：grid=[[1,3,1],[1,5,1],[4,2,1]]输出：7解释：因为路径1→3→1→1→1的总和最小。示例2：输入：grid=[[1,2,3],[4,5,6]]输出：12提示：m==grid.lengthn==grid[i].length10二、解题思路二维的动态规则，定义一个二维dp数组，其中dp[i][j]
本题为12月30日22寒假集训每日一题题解题目来源:(未知)题面题目描述懒羊羊和小灰灰在玩一种棋盘游戏，棋盘的尺寸为n个方格*m个方格。一开始在棋盘的右上角（1，m）放一枚硬币，每次一个人可以将硬币向左、下或左下的方格移动。当某个人无法再移动硬币了，那么这个人就输了。游戏总是懒羊羊先开始，如果他们两个每步都是最优策略，则谁将赢得游戏？输入输入包含多组测试数据。每组输入两个整数n和m（0当n=m=0时，输入结束。输出对于每组输入，如果懒羊羊赢，输出“Wonderful!”，否则输出“Whatapity!”。样例输入Copy53546600样例输出CopyWhatapity!Wonderful!W
本题为12月30日22寒假集训每日一题题解题目来源:(未知)题面题目描述懒羊羊和小灰灰在玩一种棋盘游戏，棋盘的尺寸为n个方格*m个方格。一开始在棋盘的右上角（1，m）放一枚硬币，每次一个人可以将硬币向左、下或左下的方格移动。当某个人无法再移动硬币了，那么这个人就输了。游戏总是懒羊羊先开始，如果他们两个每步都是最优策略，则谁将赢得游戏？输入输入包含多组测试数据。每组输入两个整数n和m（0当n=m=0时，输入结束。输出对于每组输入，如果懒羊羊赢，输出“Wonderful!”，否则输出“Whatapity!”。样例输入Copy53546600样例输出CopyWhatapity!Wonderful!W
P8548小挖的买花（双重限制之限制一个最大一个最小）题目传送门：小挖的买花题解题目分析这道题目是一个多重限制的01背包变种，而且一个限制是限制最大，另一个是限制最小三维状态表示方式：dp[i][j][k],表示前i朵花，费用最大为j，新鲜度最少为k的状态中美丽度最大的状态状态转移：转移方式不选第i枝花直接由dp[i-1][j][k]转移来选第i枝花(判断是否满足限制金额大于等于第i枝花的金额)1.当前的花(第i枝花)直接能满足k需求(即第i枝花的新鲜度大于k)2.第i枝花新鲜度不够k，从之前减去第i枝花金额的j和减去第i枝花新鲜度的k的状态转移过来dp[i][j][k]=dp[i-1][j]
