区间DP

石子合并

原题链接

#include <iostream>
#include <algorithm>

using namespace std;

const int N=310;
const int INF=0x3f3f3f3f;

int n;
int dp[N][N];
int s[N];


int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);
        s[i]+=s[i-1];
    }
    
    for(int len=2;len<=n;len++)//区间长度是1时合并不需要代价
    {
        for(int i=1;i+len-1<=n;i++)//枚举len下的起点位置
        {
           
            //可以算出终点位置
            int l=i,r=i+len-1;
            
            dp[l][r]=INF;
            for(int k=l;k<r;k++)//枚举分割点k
                dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
        }
    }
    
    cout<<dp[1][n]<<endl;
    return 0;
}

2.剪绳子

• 1.dp[i]表示绳子长度为i的最大乘积

• 2.由于必须切一刀，假设切在j位置，左边长度为j，则右边长度为i-j，对于右边长度，可切可不切

• 3.dp[i]=max( j * (i-j) ,j * dp[i-j] )

class Solution {
public:
    int maxProductAfterCutting(int length) {
        int dp[length+10];
        memset(dp,0,sizeof dp);
        for(int i=2;i<=length;i++)
        {
            for(int j=1;j<i;j++)
            {
                dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[length];
    }
};