LeetCode(C++)-动态规划(使用最小花费爬楼梯、不同路径、不同路径 II、整数拆分、不同的二叉搜索树)_c++最小花费

746. 使用最小花费爬楼梯

代码：

class solution {	//746. 使用最小花费爬楼梯
	//1. 确定dp数组以及下标的含义：dp[i]到达第i个台阶的最少花费
	//2. 确定递推公式：dp[i]=min(dp[i-1],dp[i-2])+cost[i]
	//3. dp数组如何初始化：dp[0]=cost[0],dp[1]=cost[1]
	//4. 确定遍历顺序：从前往后遍历cost数组
	//5. 举例推导dp数组：cost:[1,100,1,1,1,100,1,1,100,1] dp:1,100,2,3,3,103,4,5,104,6  在104和6之间取最小
public:
	int mincostclimbingstairs(vector<int>& cost) {
		vector<int> dp(cost.size());
		dp[0] = cost[0];
		dp[1] = cost[1];
		for (int i = 2; i < cost.size(); ++i) {
			dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
		}
		return min(dp[cost.size() - 1], dp[cost.size() - 2]);
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

62. 不同路径

代码：

class Solution {	//62. 不同路径
	//动态规划五部曲：
	//1. 确定dp数组以及下标的含义：d[i][j] 为从起点到位置（i,j）有d[i][j]种方法
	//2. 确定递推公式：d[i][j]=d[i-1][j]+d[i][j-1]
	//3. dp数组如何初始化：d[i][0]=1,i>=0,i<m;d[0][j]=1,j>=0,j<n;
	//4. 确定遍历顺序：每一个位置的方法数都是由它的上方位置和左方位置方法数相加得到，从左到右一层层遍历
	//5. 举例推导dp数组：
public:
	int uniquePaths(int m, int n) {
		vector<vector<int>> dp(m, vector<int>(n, 0));
		for (int i = 0; i < m; ++i) {
			dp[i][0] = 1;
		}
		for (int j = 0; j < n; ++j) {
			dp[0][j] = 1;
		}

		for (int i = 1; i < m; ++i) {
			for (int j = 1; j < n; ++j) {
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
		}
		return dp[m - 1][n - 1];
	}
};
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

63. 不同路径 II

代码：

class Solution {	//63. 不同路径 II
	//动态规划五部曲：
	//1. 确定dp数组以及下标的含义：d[i][j] 为从起点到位置（i,j）有d[i][j]种方法
	//2. 确定递推公式：有障碍物的位置为dp[i][j]=0，没有障碍物d[i][j]=d[i-1][j]+d[i][j-1]
	//3. dp数组如何初始化：d[i][0]=1,i>=0,i<m;d[0][j]=1,j>=0,j<n; 如果障碍物在最上面或者最左面，那么上面障碍物右侧都为0或左面障碍物下侧都为0
	//4. 确定遍历顺序：每一个位置的方法数都是由它的上方位置和左方位置方法数相加得到，从左到右一层层遍历
	//5. 举例推导dp数组
public:
	int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
		int m = obstacleGrid.size();
		int n = obstacleGrid[0].size();
		vector<vector<int>> dp(m, vector<int>(n, 0));
		for (int i = 0; i < m; ++i) {
			if (obstacleGrid[i][0] == 1) break;
			else dp[i][0] = 1;
		}
		for (int j = 0; j < n; ++j) {
			if (obstacleGrid[0][j] == 1) break;
			else dp[0][j] = 1;
		}

		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];
				}
			}
		}
		return dp[m - 1][n - 1];
	}
};
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

343. 整数拆分

代码：

class Solution {	//343. 整数拆分
	//1. 确定dp数组以及下标的含义：将i拆分后，得到的最大乘积和为dp[i]
	//2. 确定递推公式：dp[i]由两种方式得到，一是j*(i-j)，拆成两份；二是j*dp[i-j]，拆成两个及以上，然后在遍历的过程中，dp[i]会不断更新，直到取到最大的
	// 所以递推公式为：dp[i]=max(dp[i], max(j*(i-j)，j*dp[i-j]))
	//3. dp数组如何初始化：dp[2]=1
	//4. 确定遍历顺序：dp[i]依靠dp[i-j]的状态，所以遍历从前向后，枚举j时从1开始，i从3开始，dp[i-j]就是dp[2]正好可以通过初始化数值求出来
	//5. 举例推导dp数组：i从2到10，dp[i]依次为：1,2,4,6,9,12,18,27,36
public:
	int integerBreak(int n) {
		vector<int> dp(n + 1);
		dp[2] = 1;
		for (int i = 3; i <= n; ++i) {
			for (int j = 1; j < i - 1; ++j) {
				dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
			}
		}
		return dp[n];
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

96. 不同的二叉搜索树

代码：

class Solution {	//96. 不同的二叉搜索树
	//动态规划五部曲：
	//1. 确定dp数组以及下标的含义：恰由i个节点组成且节点值从1到i互不相同的二叉搜索树有dp[i]种
	//2. 确定递推公式：dp[i]+=dp[j-1]*dp[i-j],j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量
	//3. dp数组如何初始化：dp[0]=1,空节点也算一棵树
	//4. 确定遍历顺序：节点数为i的状态依靠i之前的节点数的状态，遍历i里面每一个数作为头结点的状态，用j来遍历
	//5. 举例推导dp数组：i从0到4 dp[i]为1,1,2,5,14
public:
	int numTrees(int n) {
		vector<int> dp(n + 1);
		dp[0] = 1;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= i; ++j) {
				dp[i] += dp[j - 1] * dp[i - j];
			}
		}
		return dp[n];
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

参考资料：

代码随想录