题目:

P1806 跑步 - 洛谷

思路:

创建long long dp[n][m]二维数组,其值代表跑n圈,以m圈为结束圈数的总方案数。

状态转移方程:dp[i][j]+=dp[i-j][k],第一维(i  和  i-j)代表跑的总圈数,第二维(j  和  k)代表最后跑的圈数。

在确定了跑i圈的最后一圈为j之后,我们只需枚举总圈数跑i-j(跑j圈之前我们跑的总圈数)圈时,最后一圈跑小于j的k值(k<j保证了后面一圈跑得圈数比前一圈跑得圈数大).

至于为什么得初始化dp[i][i]=1(dp[i][i]代表一次性跑完,题中不包括这种情况),我认为是为了解决将圈数划分为两部分跑时所出现的问题(且后续的一切划分方法都是基于划分成两部分所得来的)

比如: n=5时,有 2  3      和      1  4两种划分方法

i=5,j=3,i-j=2,k=2     dp[5][3]+=dp[2][2];这代表以2  3的方式跑完5圈,这必然是跑完5圈的方法之一, 但若我们不赋值给dp[2][2],那么dp[2][2]=0,但这显然与上述矛盾(dp[5][3]+=0无法使得跑5圈以2  3的方式跑),故我们给它赋1.后续只需在最后的结果中减去一次性跑完的划分方法即可。

同理dp[5][4]+=dp[1][1]也是这样的情况。

代码:

#include<bits/stdc++.h>
using namespace std;
long long dp[505][505];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)dp[i][i]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            for(int k=1;k<j;k++){
                dp[i][j]+=dp[i-j][k];
            }
        }
    }
    long long ans=0;
    for(int i=1;i<=n;i++){
        ans+=dp[n][i];
    }
    cout<<ans-1;
    return 0;
}

结语:

感谢阅读