动态规划">动态规划
动规五部曲：
- 确定dp数组以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
70. 爬楼梯 - 力扣（LeetCode）
爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。
那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。
所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。
我们来分析一下，动规五部曲：
定义一个一维数组来记录不同楼层的状态
- 确定dp数组以及下标的含义
dp[i]： 爬到第i层楼梯，有dp[i]种方法
- 确定递推公式
如何可以推出dp[i]呢？
从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。
首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。
还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。
那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！
所以dp[i] = dp[i - 1] + dp[i - 2] 。
在推导dp[i]的时候，一定要时刻想着dp[i]的定义，否则容易跑偏。
class Solution {
public int climbStairs(int n) {
if(n==1||n==2) return n;
int[] dp=new int[n+1];
dp[0]=1;
dp[1]=1;
//dp[2]应该是2
dp[2]=2;
for(int i=3;i<=n;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
}746. 使用最小花费爬楼梯 - 力扣（LeetCode）
题目没说明白，脑残的很
class Solution {
public int minCostClimbingStairs(int[] cost) {
//这个题他爹的有毛病 cost的长度是n 但是楼梯下标要到n 长度为n+1
if(cost.length==2) return Math.min(cost[0],cost[1]);//只有1极楼梯
int n=cost.length;
//dp表示到达此处的最小花费
int[] dp=new int[n+1];
dp[0]=0;
dp[1]=0;//因为可以选择从0或者1出发
for(int i=2;i<=n;i++)
{
dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[n];
}
}63. 不同路径 II - 力扣（LeetCode）
和62不同路径一样 先初始化横竖两排，然后判断一下有障碍的地方dp就是0
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m=obstacleGrid.length;
int n=obstacleGrid[0].length;
int[][] dp=new int[m][n];
//如果第一行或第一列中存在障碍物，那么障碍物之后的路径数量应该是0，而不是1。
for(int i=0;i<obstacleGrid.length;i++)
{
if(obstacleGrid[i][0]==0)
{
dp[i][0]=1;
}else{
break;
}
}
for(int j=0;j<obstacleGrid[0].length;j++)
{
if(obstacleGrid[0][j]==0)
{
dp[0][j]=1;
}else{
break;
}
}
for(int i=1;i<m;i++)
{
for(int j=1;j<n;j++)
{
if(obstacleGrid[i][j]!=1)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}else{
dp[i][j]=0;
}
}
}
return dp[m-1][n-1];
}
}
118. 杨辉三角 - 力扣（LeetCode）
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res=new ArrayList<>();
res.add(List.of(1));
for(int i=1;i<numRows;i++)
{
List<Integer> row=new ArrayList<>(i+1);//i+1是元素数量
//第一个是1
row.add(1);
for (int j = 1; j < i; j++) {
// 左上方的数 + 正上方的数
row.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
}
//最后一竖是1
row.add(1);
res.add(row);
}
return res;
}
}**343. 整数拆分 - 力扣（LeetCode）
class Solution {
public int integerBreak(int n) {
//dp[i] 为正整数 i 拆分后的结果的最大乘积
int[] dp = new int[n+1];
dp[1]=1;
dp[2]=1;
for(int i = 3; i <= n; i++) {
for(int j = 1; j < i;j++) {
//如果在比较最大值的时候不包括dp[i]，那有可能越比越小，倒把一开始找到的最大值给弄丢了
dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
// j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ，再相乘
//而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
}
}
return dp[n];
}
}
198. 打家劫舍 - 力扣（LeetCode）
动态规划的的四个解题步骤是：
- 定义子问题
- 写出子问题的递推关系
- 确定 DP 数组的计算顺序
- 空间优化（可选）
class Solution {
public int rob(int[] nums) {
if(nums.length==1) return nums[0];
if(nums.length==2) return Math.max(nums[0],nums[1]);
//只有两种状态 偷窃或者不偷窃
int[] dp=new int[nums.length];
//表示两种状态中最大获利
dp[0]=nums[0];
// dp[1]=nums[1];不对哦
dp[1]=Math.max(dp[0],nums[1]);
//列出状态转移方程
for(int i=2;i<nums.length;i++)
{
dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
}
return dp[nums.length-1];
}
}首先「完全平方数」有无限个，但要凑成的数字是给定的。
所以首先把所有可能用到的「物品」预处理出来。
从而将问题转换为：给定了若干个数字，每个数字可以被使用无限次，求凑出目标值n所需要用到的是最少数字个数是多少。
152. 乘积最大子数组 - 力扣（LeetCode）
class Solution {
public int maxProduct(int[] nums) {
int max = Integer.MIN_VALUE, imax = 1, imin = 1;
for(int i=0; i<nums.length; i++){
if(nums[i] < 0){
//由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值imin
//在出现负数这种危机关头计算最大最小
int tmp = imax;
imax = imin;
imin = tmp;
}
imax = Math.max(imax*nums[i], nums[i]);//一旦前面有负数就放弃曾经的一切
imin = Math.min(imin*nums[i], nums[i]);
max = Math.max(max, imax);
}
return max;
}
}
