前置知识

参考前文

参考文章：
LeetCode刷题笔记【29】：动态规划专题-1（斐波那契数、爬楼梯、使用最小花费爬楼梯）
LeetCode刷题笔记【30】：动态规划专题-2（不同路径、不同路径 II）

343. 整数拆分

题目描述

LeetCode链接：https://leetcode.cn/problems/integer-break/description/

解题思路

思路: 动态规划
建立dp数组, 表示下标i的最大乘积
对每个新的i, 将i分成(i=x+y), dp[i] = max(dp[x], x) * max(dp[y], y);

代码

class Solution {
public:int integerBreak(int n) {vector<int> dp(n+1, INT_MIN);dp[0] = 0;dp[1] = 0;dp[2] = 1;if(n<=2)return dp[n];for(int i=3; i<=n; ++i){for(int x=1; x<=i/2; ++x){int y = i-x;dp[i] = max(dp[i], max(dp[x], x) * max(dp[y], y));}}return dp[n];}
};

进一步优化

可以将递推构建dp数组的过程进一步简化为以下形式
效率会更高, 但是理解起来困难一些, 也不容易想到

for (int i = 3; i <= n ; i++) {for (int j = 1; j <= i / 2; j++) {dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));}
}

96.不同的二叉搜索树

题目描述

LeetCode链接：https://leetcode.cn/problems/unique-binary-search-trees/description/

解题思路

动态规划
dp数组中dp[i]表示有i个节点的时候有dp[i]种搜素树
dp[0]=0, dp[1]=1, dp[2]=2
求dp[i]的时候, 用j遍历1到i, dp[i] += dp[j-1] * dp[i-j];

代码

class Solution {
public:int numTrees(int n) {vector<int> dp(max(n+1,5),0);dp[0] =1;dp[1] = 1;dp[2] = 2;if(n<=2)return dp[n];for(int i=3; i<=n; ++i){for(int j=1; j<=i; ++j){dp[i] += dp[j-1] * dp[i-j];}}return dp[n];}
};

优化改进

不用初始化到2, 到1就行了

class Solution {
public:int numTrees(int n) {vector<int> dp(n+1,0);dp[0] =1;dp[1] = 1;for(int i=2; i<=n; ++i){for(int j=1; j<=i; ++j){dp[i] += dp[j-1] * dp[i-j];}}return dp[n];}
};

总结

很多动态规划题目, 因为涉及到递推, 前后数值的查询, 所以直接脑中空想比较困难;
想不清楚的时候最好动笔写写画画, 思路会清晰很多.

本文参考：
整数拆分
不同的二叉搜索树