本文主要是介绍代码随想录day41| 343. 整数拆分 、96.不同的二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
343. 整数拆分
dp[i]：对i进行拆分，相乘得到的最大值dp[i]
递推公式：
dp[i] = max(dp[i], j * (i - j), j * dp[i - j]);为什么还要dp[i[放进去比较？
——这其实是在不断更新dp[i]的值，不放进的话，原本的dp[i]会直接被舍弃
初始化：dp[0]和dp[1]都是没有意义的，所以初始化为零，dp[2]=1
为什么只需要对i-j进行拆分？
——这里类似于一个组合问题，当就j > i/2时，情况就开始重复出现了
遍历顺序：从前向向后
int *initDP(int num){int* dp = (int*)malloc(sizeof(int)*(num + 1));int i; for(i = 0; i < num + 1; ++i){dp[i] = 0;}return dp;
}
int max(int num1, int num2, int num3){int tempMax = num1 > num2 ? num1 : num2;return tempMax > num3 ? tempMax : num3;
}
int integerBreak(int n) {int *dp = initDP(n);dp[2] = 1;int i;for(i = 3; i <= n; ++i){int j;for(j = 1; j < i - 1; ++j){dp[i] = max(dp[i], j * (i - j), j* dp[i-j]);}}return dp[n];
}96. 不同的二叉搜索树
dp[i]:输入i时， 有dp[i]种情况
递推公式：dp[i]+=dp[j-1]*dp[i-j];——有多少种二叉树，是左子树的数量乘上右子树的数量，由于二叉搜索树的原因，左子树肯定是有j,右子树是i-j
初始化：dp[0] = 1，dp[1] =1因为根结点为0或1是所有二叉树的种类之一，其余都要初始化为零，因为要不断的累加，所以说要从零开始累加
遍历顺序：从前向后
int *initDP(int n){int *dp = (int*)malloc(sizeof(int)*(n + 1));int i;for(i = 0; i <= n; ++i){dp[i] = 0;}return dp;
}
int numTrees(int n) {int *dp = initDP(n);dp[0] = 1;int i,j;for(i = 1; i <= n; ++i){for(j = 1; j <= i; ++j){dp[i] += dp[j - 1]*dp[i - j];}}return dp[n];
}这篇关于代码随想录day41| 343. 整数拆分 、96.不同的二叉搜索树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
