Write some DP

Title Description

When Zhenzhen learns multiplication , Find out 4=2*2,9=3*3,…, and 2 It is impossible to decompose into the product of two identical integers , But it can be broken down into 1*1+1*1. She wants to know for any positive integer n, Divide it into several integers and multiply it by itself , How many options are there ？

Input

There is only one line of input , This line has only one positive integer n.

Output

There is only one line of output , This line has only one positive integer , Represents the total number of schemes .

The sample input  Copy

13

Sample output  Copy

6

Tips

30% The data of ,1≤n≤10; 
80% The data of ,1≤n≤300;
100% The data of ,1≤n≤800.

  A two-dimensional dp

#include <bits/stdc++.h>
using namespace std;
int n,i,j;
int k;
int a[35];
int dp[905][905];
void solve()
{
    dp[0][0]=1;
    for(i=1;i<=30;i++)
    {
        for(j=0;j<=k;j++)
        {
            for(int t=0;t*a[i]<=j;t++)
            {
                dp[i][j]+=dp[i-1][j-t*a[i]];
            }
        }
    }
    printf("%d",dp[30][k]);
}
int main()
{
    cin>>k;
for(i=1;i<=30;i++)
{
    a[i]=i*i;
}
solve();

    return 0;
}

A one-dimensional dp

#include <bits/stdc++.h>
using namespace std;
int n,i,j;
int k;
int a[35];
int dp[905];
void solve()
{
    dp[0]=1;
    for(i=1; i<=30; i++)
    {
        for(j=k;j>=0;j--)// Write it right upside down , It's written incorrectly 
        {
            for(int t=1; t*a[i]<=j; t++)
            {
                dp[j]+=dp[j-t*a[i]];
            }
        }
    }
    printf("%d",dp[k]);
}
int main()
{
    cin>>k;
    for(i=1; i<=30; i++)
    {
        a[i]=i*i;
    }
    solve();

    return 0;
}