整数拆分~

way：process

//上一个拆出来的数是pre
//还剩下rest需要去拆
//返回拆解的方法数

#include<iostream>
using namespace std;//上一个拆出来的数是pre
//还剩下rest需要去拆
//返回拆解的方法数
int process(int pre, int rest)
{if(rest==0) return 1;//因为后面的数只会越来越大if(pre>rest) return 0;int ways=0;for(int x=pre; x<=rest; x++){ways+=process(x, rest-x);}return ways;
}//num为正数
int numSplit(int num)
{if(num<0) return 0;if(num==1) return 1;return process(1,num-1);
}

way2：dp版，初始化，dp过程，值得注意。

int dpWay(int num)
{if(num<0) return 0;if(num==1) return 1;vector<vector<int>>dp(num+1, vector<int>(num+1));for(int pre=1; pre<=num; pre++){dp[pre][0]=1;dp[pre][pre]=1;}for(int pre=num-1; pre>=1; pre--){//rest一定大于prefor(int rest=pre+1; rest<=num; rest++){int ways=0;for(int x=pre; x<=rest; x++){ways+=dp[x][rest-x];}dp[pre][rest]=ways;}}return dp[1][num-1];
}