动态规划学习记录：题型/思路汇总

发表于 分类于 阅读次数： 本文字数： 5.5k 阅读时长 ≈ 20 分钟

动态规划学习记录

记录了常见的一维与二维动态规划题目 & 题解。

一维数组动态规划

  • 一般来说这类题数据都是一维的。例如只受价格影响，如果像01背包问题那样的受价格和大小两个数据影响，就是二维的动态规划。一维动态规划的状态转移方程一般都是平级移动，受之前状态的影响，相对较简单。

1.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs OJ链接
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
思路很简单，因为一次只能跳一格或者两格，所以当前阶数可前往的方法数等于前两阶的方法数之和。

状态转移方程为：
dp[now] = dp[now-1] + dp[now-2];

AC代码：

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
#include<bits/stdc++.h>
using namespace std;

class Solution 
{
public:
    int climbStairs(int n) 
	{
		int *dp = new int[n+10],t;
		dp[1]=1;
		dp[2]=2;
		for(int now=3;now<=n;now++)
		{
			dp[now] = dp[now-1]+dp[now-2];
		}
		t = dp[n];
		delete[] dp;
		return t;
    }
};

int main()
{
	int n;
	cin>>n;
	Solution s;
	cout<<s.climbStairs(n);
	return 0;
}

2.数硬币

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。

示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

示例 2：
输入：coins = [2], amount = 3
输出：-1

示例 3：
输入：coins = [1], amount = 0
输出：0

示例 4：
输入：coins = [1], amount = 1
输出：1

示例 5：
输入：coins = [1], amount = 2
输出：2

提示：
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change OJ链接
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

当前金额的最小需要硬币数，等于当前金额分别减去硬币面额的所需最小硬币数的最小值加一。例如求2,5,7面额硬币凑27块钱所需的最少硬币，就得求20块钱、22块钱、25块钱的最少硬币(27-7 27-5 27-2)，找到其中的最小值加一就是27块钱所需的最小硬币数。而20块钱，22块钱，25块钱的最少硬币数就按这个倒推，最终可以求出所有金额所需的最小硬币数。

状态转移方程为：
dp[x] = x金额的所需最少硬币数;
dp[now] = min( (now-coin[0])+1, (now-coin[1])+1, …… (now-coin[end])+1 );
最终结果为: dp[amount];

AC代码：

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
class Solution {
public:
    int func(int *z,vector<int>& coins,int d)
    {
        int temp=9999999;
        for(int now=0;now<coins.size();now++)
        {
            if(d-coins[now]>=0)
            {
                temp=min(temp,z[d-coins[now]]);
            }
        }
        return temp+1;
    }
    int coinChange(vector<int>& coins, int amount) 
    {
        int *count=new int[amount+1];
	
        count[0]=0;
        
        for(int now=1;now<amount+1;now++)
        {
            count[now]=func(count,coins,now);
            //printf("%d\n",count[now]);
        }
        return count[amount]==10000000 ? -1 : count[amount];
    }
};

3.最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray OJ链接
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
加一个max变量，储存最大值，dp数组储存当前连续的最大值。

状态转移方程为：
dp[now] = max(nums[now],dp[now-1]+nums[now];

AC代码：

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
#include<bits/stdc++.h>
using namespace std;

class Solution 
{
public:
    int maxSubArray(vector<int>& nums)
    {
        int *dp = new int[nums.size()+1],max_=0;
        dp[0]=nums[0];
        max_=dp[0];
        for(int now=1;now<nums.size();now++)
        {
        	
            dp[now]=max(nums[now],dp[now-1]+nums[now]);
            max_=max(max_,dp[now]);
        }
        return max_;
    }
};

int main()
{
	int a[] = {-2,1,-3,4,-1,2,1,-5,4};
	vector<int>n(a,a+9);
	Solution s;
	cout<<s.maxSubArray(n);
	return 0;
}

4.区域和检索 - 数组不可变

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。
实现 NumArray 类：
NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], … , nums[j])）

示例：

  • 输入：
    [“NumArray”, “sumRange”, “sumRange”, “sumRange”]
    [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
  • 输出：
    [null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

提示：
0 <= nums.length <= 104
-105 <= nums[i] <= 105
0 <= i <= j < nums.length
最多调用 104 次 sumRange 方法

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/range-sum-query-immutable OJ链接
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
用dp数组记录前x个数的和，求i ~ j区间的值的和即为dp[j+1] - dp[i];

状态转移方程：
dp[now]代表前now个数字的和；
dp[now] = dp[now-1] + nums[now-1];

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class NumArray {
public:
    NumArray(vector<int>& nums) 
    {
        dp.resize(nums.size()+10,0);
        for(int i=1;i<=nums.size();i++)
        {
            dp[i]=dp[i-1]+nums[i-1];
        }
    }
    
    int sumRange(int i, int j) 
    {
        return dp[j+1]-dp[i];
    }
private:
    vector<int> dp;
};

5.整数拆分

定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-break OJ地址
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路： 遍历所有可能的分割结果。

状态转移方程为：
dp[x] = 整数为x时的最大组合乘积;
初始dp[1]=1;即1的整数最大乘积是1;
dp[x] = max( max( dp[x-1] * 1, (x-1) * 1 ), max( dp[x-2] * 2, (x-2) * 2 ), max( dp[x-3] * 3, (x-3) * 3 ), …… max( dp[1] * (x-1), 1 * (x-1) );
最终结果为: dp[n];

AC代码：

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
#include<bits/stdc++.h>
using namespace std;

class Solution 
{
public:
    int integerBreak(int n) 
	{
		int *count = new int[n+1],temp=0; 
		count[1]=1;
		for(int now=2;now<n+1;now++)
		{
			temp=0;
			for(int t1=1;t1<now;t1++)
			{
				temp=max(temp,count[now-t1]*t1);
				temp=max(temp,(now-t1)*t1);
			}
			count[now]=temp;
			//cout<<count[now]<<endl;
		}
		return count[n];
    }
};

int main()
{
	int n;
	cin>>n;
	
	Solution s;
	cout<<s.integerBreak(n);
		
	return 0;
}

6.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：
0 <= nums.length <= 100
0 <= nums[i] <= 400

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber OJ链接
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路： 可简单看出最大值是在不偷前一个屋子加上偷当前屋子和不偷当前屋子和偷前一个屋子之间做选择。

状态转移方程为：
dp[x] = 偷到x号房子时的最大可偷最大价值;
初始dp[0]=0,dp[1]=nums[0];
即不偷的时候价值为0，只偷一个屋子时价值最大为第一个屋子;
dp[x] = max( dp[x-2]+nums[x], dp[x-1] );
最终结果为: dp[nums.size()];

AC代码：

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
38
39
40
#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int rob(vector<int>& nums) 
	{
		int *dp = new int[nums.size()+1];
		if(nums.size()>=1)
		{
			dp[0]=0,dp[1]=nums[0];
			for(int now=2;now<=nums.size();now++)
			{
				dp[now] = max(dp[now-2]+nums[now-1],dp[now-1]);
				//cout<<dp[now]<<endl;
			}
			return dp[nums.size()];
		}
		else
		{
			return 0;
		}
    }
};

int main()
{
	vector<int>n; 
	int t;
	
	while(scanf("%d",&t)!=EOF)
	{
		n.push_back(t);
	}
	
	Solution s;
	cout<<s.rob(n);
		
	return 0;
}

7.打家劫舍II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下 ，能够偷窃到的最高金额。

示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：
输入：nums = [0]
输出：0

提示：
1 <= nums.length <= 100
0 <= nums[i] <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-ii OJ链接
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路： 在上一题的基础上，增加了环的概念。大致就是有首不能有尾，有尾不能有首。我们可以先求{1，n-1}这个区间的最大值，再求{2，n}这个区间的最大值，然后取这两个值中的最大值，即为本题答案。

AC代码： 

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
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int rob(vector<int>& nums) 
	{
		int *dp = new int[nums.size()+1];
		int *dp2 = new int[nums.size()+1];
		if(nums.size()>=1)
		{
			dp[0]=0,dp[1]=nums[0];// 0 ~ n-1
			for(int now=2;now<=nums.size()-1;now++)
			{
				dp[now] = max(dp[now-2]+nums[now-1],dp[now-1]);
				//cout<<dp[now]<<endl;
			}
			dp2[0]=0,dp2[1]=0;// 1 ~ n
            for(int now=2;now<=nums.size();now++)
			{
				dp2[now] = max(dp2[now-2]+nums[now-1],dp2[now-1]);
				//cout<<dp[now]<<endl;
			}
			if(nums.size()>1)
				dp[nums.size()]=max(dp[nums.size()-1],dp2[nums.size()]);
			return dp[nums.size()];
		}
		else
		{
			return 0;
		}
    }
};

int main()
{
	vector<int>n; 
	int t;
	
	while(scanf("%d",&t)!=EOF)
	{
		n.push_back(t);
	}
	
	Solution s;
	cout<<s.rob(n);
		
	return 0;
}

8.解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码：
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
题目数据保证答案肯定是一个 32 位的整数。

示例 1：
输入：”12”
输出：2
解释：它可以解码为 “AB”（1 2）或者 “L”（12）。

示例 2：
输入：”226”
输出：3
解释：它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

示例 3：
输入：s = “0”
输出：0

示例 4：
输入：s = “1”
输出：1

示例 5：
输入：s = “2”
输出：1

提示：
1 <= s.length <= 100
s 只包含数字，并且可以包含前导零。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-ways OJ链接
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

AC代码：

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:
    int numDecodings(string s) 
    {
        int *dp = new int[s.size()+1];
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        s[0]=='0' ? dp[1]=0 : dp[1]=1;
        for(int now=2;now<=s.size();now++)
        {
        	if(s[now-1]!='0')
        	{
        		if(s[now-2]=='1'||(s[now-2]=='2'&&s[now-1]<='6'))
        		{
        			dp[now]=dp[now-1]+dp[now-2];
        			
				}
				else
				{
					dp[now]=dp[now-1];
				}
			}
			else
			{
				if(s[now-2]=='2'||s[now-2]=='1')
				{
					dp[now]=dp[now-2];
				}
				else
				{
					return 0;
				}
			}
		}
		return dp[s.size()];
    }
};

9.乘积最大字数组

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray OJ链接
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxProduct(vector<int>& nums) 
    {
        int dp_max[nums.size()+10],dp_min[nums.size()+10];
        dp_max[1]=nums[0];
        dp_min[1]=nums[0];
        for(int now=2;now<=nums.size();now++)
        {
            dp_max[now] = max(dp_min[now-1]*nums[now-1], dp_max[now-1]*nums[now-1]);
            dp_max[now] = max(dp_max[now], nums[now-1]);
            dp_min[now] = min(dp_max[now-1]*nums[now-1], dp_min[now-1]*nums[now-1]);
            dp_min[now] = min(dp_min[now], nums[now-1]);
        }
        int max_ = INT_MIN;
        for(int now=1;now<=nums.size();now++)
        {
            max_ = max(max_,dp_max[now]);
        }
        return max_;
    }
};

10.完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.

示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/perfect-squares OJ链接
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numSquares(int n) 
    {
        int dp[n+1],t=1;
        memset(dp,9999,sizeof(dp));
        dp[0] = 0;
        for(int now=1;now<=n;now++)
        {
            t=1;
            while(t*t<=now)
            {
                dp[now] = min(dp[now],dp[now-t*t]+1);
                t++;
            }
        }
        return dp[n];
    }
};

二维数组动态规划

  • 这类的dp题有两个影响结果的数值，例如01背包问题里的价值和大小、空间问题里的x,y坐标等等都是二维的数据。这种题建立dp数组的时候，就需要构建二维的dp数组，并且状态转移方程的变化情况也更加多样，相对较难一点。

1.不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？

图1

例如，上图是一个7 x 3 的网格。有多少可能的路径？

示例 1:

  • 输入: m = 3, n = 2
  • 输出: 3
    解释:
    从左上角开始，总共有 3 条路径可以到达右下角。
  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向右

示例 2:

  • 输入: m = 7, n = 3
  • 输出: 28

提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths OJ链接
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路： dp构建表格，dp[x][y]代表在x,y坐标时的可前往路程数。由于方格只能向下或者向右走，所以前往某一格的方案数，就是前往上一格和左一格的方案数之和。

状态转移方程：
dp[x][y] = dp[x-1][y]+dp[x][y-1];
最终结果为: dp[X][Y];

AC代码： OJ链接

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
#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int uniquePaths(int m, int n) 
    { 
        int dp[101][101];   
        memset(dp,0,sizeof(dp));
        dp[1][1]=1;
        for(int now=1;now<=m;now++)
        {
            for(int now1=1;now1<=n;now1++)
            {
                if(now-1>=1)
                {
                    dp[now][now1]+=dp[now-1][now1];
                }
                if(now1-1>=1)
                {
                    dp[now][now1]+=dp[now][now1-1];
                }	
            }
        }
        return dp[m][n];
    }
};

int main()
{
	Solution s;
	cout<<s.uniquePaths(7,3);
	return 0;
}

2.不同路径II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
图2

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

  • 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
  • 输出：2
    解释：
    3x3 网格的正中间有一个障碍物。
    从左上角到右下角一共有 2 条不同的路径：
  1. 向右 -> 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

  • 输入：obstacleGrid = [[0,1],[0,0]]
  • 输出：1

提示：
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-ii OJ链接
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
在上一题的基础上，增加一个判断即可，当遍历到障碍格时，直接跳过不计数即可。令障碍格的可到达方法为0。

状态转移方程：
dp[x][y] = dp[x-1][y]+dp[x][y-1];
最终结果为: dp[X][Y];

AC代码：

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
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
    { 
        int dp[101][101];   
        memset(dp,0,sizeof(dp));
        dp[1][1]=1;
        for(int now=1;now<=obstacleGrid.size();now++)
        {
            for(int now1=1;now1<=obstacleGrid[0].size();now1++)
            {
            	if(obstacleGrid[now-1][now1-1]==0)
                {
                	if(now-1>=1)
	                {
	                    dp[now][now1]+=dp[now-1][now1];
	                }
	                if(now1-1>=1)
	                {
	                    dp[now][now1]+=dp[now][now1-1];
	                }	
				}
				else
				{
					dp[now][now1]=0;	
				}	
            }
        }
        return dp[obstacleGrid.size()][obstacleGrid[0].size()];
    }
};

3.最小路径和

给定一个包含非负整数的 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.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum OJ链接
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
由于只能向下或者向右移动，所以前往一个格子的最小路径，就是其上一个格子和左一个格子的较小路径和加上这个格子的权值。

状态转移方程：
dp[x][y] = min(dp[x-1][y], dp[x][y-1]) + grid[x][y];

AC代码：

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
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) 
    {
        int dp[201][201];   
        memset(dp,0,sizeof(dp));
        dp[0][0]=grid[0][0];
        for(int now=0;now<grid.size();now++)
        {
            for(int now1=0;now1<grid[now].size();now1++)
            {
            	if(now!=0&&now1!=0)
                {
                    dp[now][now1] = min(dp[now-1][now1],dp[now][now1-1]) + grid[now][now1];
                }
                else if(now==0&&now1!=0)
                {
                    dp[now][now1] = dp[now][now1-1] + grid[now][now1];
                }
                else if(now!=0&&now1==0)
                {
                    dp[now][now1] = dp[now-1][now1] + grid[now][now1];
                }
            }
        }
        return dp[grid.size()-1][grid[0].size()-1];
    }
};

4.三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

例如，给定三角形：

1
2
3
4
5
6
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/triangle OJ链接
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
建立二维数组，储存到达每一个坐标的最小路径值。最后遍历最后一行的最小值，即为最终答案。

状态转移方程：
对于行首元素：
dp[x][0] = dp[x-1][0] + triangle[x][0];
对于行尾元素：
dp[x][x] = dp[x-1][x-1] + triangle[x][x];
对于行中元素：
dp[x][y] = min(dp[x-1][y-1], dp[x-1][y]) + triangle[x][y];

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) 
    {
        int dp[triangle.size()][triangle.size()];
        memset(dp,0,sizeof(dp));
        dp[0][0]=triangle[0][0];
        for(int now=1;now<triangle.size();now++)
        {
            dp[now][0]=dp[now-1][0]+triangle[now][0];
            dp[now][now]=dp[now-1][now-1]+triangle[now][now];
            for(int t=1;t<=now-1;t++)
            {
                dp[now][t] = min(dp[now-1][t-1],dp[now-1][t]) + triangle[now][t]; 
            } 
        }
        int min_=INT_MAX;
        for(int now=0;now<triangle.size();now++)
        {
            min_=min(dp[triangle.size()-1][now],min_);
        }
        return min_;
    }
};

5.最大正方形

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

示例：

1
2
3
4
5
6
7
输入：
matrix = [["1","0","1","0","0"],
          ["1","0","1","1","1"],
          ["1","1","1","1","1"],
          ["1","0","0","1","0"]]

输出：4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-square OJ链接
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

AC代码：

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
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) 
    {
        if(matrix.size()==0)
            return 0;
        int dp[matrix.size()+1][matrix[0].size()+1];
        int max_=0,temp;
        memset(dp,0,sizeof(dp));
        for(int x=1;x<=matrix.size();x++)
        {
            for(int y=1;y<=matrix[0].size();y++)
            {
                if(matrix[x-1][y-1]=='1')
                {
                    temp = min(dp[x-1][y-1],dp[x-1][y]);
                    temp = min(temp,dp[x][y-1]);
                    dp[x][y] = temp+1;
                    max_ = max(max_,dp[x][y]);
                }
                else
                {
                    dp[x][y] = 0;
                }
            }
        }
        return max_*max_;
    }
};