Dynamic programming of the division of numbers

1. Corresponding OJ link:

Division of Numbers_Niu Ke Tiba_Nioke Network(nowcoder.com).com)

2. Title description:

3. Problem solving ideas:

Method 1: Direct violent recursion

Try from the index position to n, please see the code for details.

Corresponding code:

class Solution {public:/*** The class name, method name and parameter name in the code have been specified, please do not modify it, just return the value specified by the method*** @param n int the number to be divided* @param k int into k parts* @return int*/int divideNumber(int n, int k) {// write code herereturn process(n, k, 1);}//Recursive meaning: the number of methods to divide n into k points starting from the index positionint process(int n, int k, int index) {if (k < 0) {return 0;}//If there are 0 points left, then there is only one division result when k is 0if (k == 0) {return n == 0 ? 1 : 0;}int ways = 0;for (int i = index; i <= n; i++) {// try the number at position iways += process(n - i, k - 1, i);}return ways;}};

Unfortunately this method will still time out even if it is changed to memoized search and dp.Let's look at the following method.It feels very good:

We can imagine k as having k boxes. According to the meaning of the title, each box cannot be empty, so we can put a 1 in each box in advance so that the box will not be empty.Then we can put the remaining n-k balls into k boxes. At this time, there are many possibilities. n-k balls can be placed in the first box, which can be placed in 1 and 2.The two boxes can also be placed in the three boxes 1 to 3, and they can also be placed in the boxes 1 to k.

Corresponding code:

class Solution {public:/*** The class name, method name and parameter name in the code have been specified, please do not modify it, just return the value specified by the method*** @param n int the number to be divided* @param k int into k parts* @return int*/vector>dp;int mod=1000000000+7;int divideNumber(int n, int k) {// write code here// dp.resize(n+1,vector>(k+1,vector(n+1,-1)));dp.resize(n+1,vector(k+1,-1));return process(n,k);}//The number of ways to divide n into k pointsint process(int n, int k){if(n==k){return 1;}if(k>n){return 0;}if(dp[n][k]!=-1){return dp[n][k];}int ways=0;//The possibility of placing the remaining n-k balls in k boxes is enumeratedfor(int i=1;i<=k;i++){ways=(ways+process(n-k,i))%mod;}dp[n][k]=ways;return ways;}};

Slope optimization:

Corresponding code:

class Solution {public:/*** The class name, method name and parameter name in the code have been specified, please do not modify it, just return the value specified by the method*** @param n int the number to be divided* @param k int into k parts* @return int*/vector>dp;int mod=1000000000+7;int divideNumber(int n, int k) {// write code here// dp.resize(n+1,vector>(k+1,vector(n+1,-1)));dp.resize(n+1,vector(k+1,-1));return process(n,k);}//The number of ways to divide n into k pointsint process(int n, int k){if(k==0){return n==0?1:0;}if(k==n){return 1;}if(k>n){return 0;}if(dp[n][k]!=-1){return dp[n][k];}int ways=process(n-1,k-1);ways=(ways+process(n-k,k))%mod;dp[n][k]=ways;return ways;}};