【动态规划DP】数组分组_计算动态规划数组怎么写

题目描述

现求出任意两数之间的余数再动态规划。
dp[i]其中i是第几个数

#include <iostream>
using namespace std;
int n;
int s[1010][1010];
int dp[1010];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i][i];
    }
    //求出任意两数之间的乘积求余
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            s[i][j]=(s[i][j-1]*s[j][j])%1000;
        }
    }
    //动态规划
    dp[0]=0;
    dp[1]=s[1][1];
    for(int i=2;i<=n;i++){
        for(int j=0;j<i;j++){
            dp[i]=max(dp[i],dp[j]+s[j+1][i]);
        }
    }
    cout<<dp[n]<<endl;
} // namespace std;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27