写点dp

题目描述

珍珍学习乘法时,发现4=2*2,9=3*3,…,而2不可能分解为二个相同整数的乘积，但可以分解为1*1+1*1。她想知道对任意的正整数n,把它分解为几个整数与自身相乘之和,有多少种方案呢？

输入

输入只有一行，该行只有一个正整数n。

输出

输出只有一行，该行只有一个正整数，表示总方案数。

样例输入 Copy

13

样例输出 Copy

6

提示

30%的数据，1≤n≤10; 
80%的数据，1≤n≤300;
100%的数据，1≤n≤800。

 二维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;
}

一维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--)//倒着写对的，正着写错的
        {
            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;
}