复杂DP经典问题的python实现

整数划分

一个正整数nn可以表示成若干个正整数之和，形如：n=n1+n2+…+nkn=n1+n2+…+nk，其中n1≥n2≥…≥nk,k≥1n1≥n2≥…≥nk,k≥1。

我们将这样的一种表示称为正整数n的一种划分。

现在给定一个正整数n，请你求出n共有多少种不同的划分方法。

输入格式

共一行，包含一个整数n。

输出格式

共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对109+7109+7取模。

数据范围

1≤n≤10001≤n≤1000

输入样例:

5

输出样例：

7

分析

两种做法

原题目题意就是从 1 ~ n 中选选任意个数 组成 n 也就是说从 1 ~ i 中选任意个数加起来等于j; 
 所以这个题就为完全背包问题的变式! 
 f[i][j] 的状态表示: i 为 从 1 ~ i 中选 总体积恰好为 j
 f[i][j] 的性质 : 数量;
 f[i][j] 的计算: 第i个物品选k个;
f[i][j] = f[i-1][j] + f[i-1][j-i] + f[i-1][j - i*2] + ....f[i-1][j-i*s];
f[i][j - i] =         f[i-1][j-i] + f[i-1][j - i*2] + ....f[i-1][j-i*s];
合并一下 f[i][j] = f[i-1][j] + f[i][j-i];
优化成一维 f[j] = f[j] + f[j-i];

#include<iostream>
#include<cstring>
using namespace std;
const int N=100005;
typedef long long LL;
const LL MOD=1e9+7;
LL dp[N];
int main()
{
    int n;
    scanf("%d",&n);
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            dp[j]=(dp[j]+dp[j-i])%MOD;
        }
    }
    printf("%lld\n",dp[n]);
    return 0;
}

#include<iostream>
using namespace std;
const int N=1005,MOD=1e9+7;
int dp[N][N];
int main()
{
    int n;
    scanf("%d",&n);
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            
            dp[i][j]=(dp[i-1][j-1]+dp[i-j][j])%MOD;
            
        }
    }
    int ans=0;
    for(int j=1;j<=n;j++)
    {
        ans=(ans+dp[n][j])%MOD;
    }
    printf("%d\n",ans);
    return 0;
}

鸣人的影分身

• 题目
• 提交记录
• 讨论
• 题解
• 视频讲解

在火影忍者的世界里，令敌人捉摸不透是非常关键的。

我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。

影分身是由鸣人身体的查克拉能量制造的，使用的查克拉越多，制造出的影分身越强。

针对不同的作战情况，鸣人可以选择制造出各种强度的影分身，有的用来佯攻，有的用来发起致命一击。

那么问题来了，假设鸣人的查克拉能量为 MM，他影分身的个数最多为 NN，那么制造影分身时有多少种不同的分配方法？

注意：

1. 影分身可以分配0点能量。
2. 分配方案不考虑顺序，例如：M=7,N=3M=7,N=3，那么 (2,2,3)(2,2,3) 和 (2,3,2)(2,3,2) 被视为同一种方案。

输入格式

第一行是测试数据的数目 tt。

以下每行均包含二个整数 MM 和 NN，以空格分开。

输出格式

对输入的每组数据 MM 和 NN，用一行输出分配的方法数。

数据范围

0≤t≤200≤t≤20,
1≤M,N≤101≤M,N≤10

输入样例：

1
7 3

输出样例：

8

分析

题目相当于是把n个苹果放m个盘子

IA=lambda:map(int,input().split())
T=int(input())
for _ in range(0,T):
    n,m=IA()
    dp=[[0 for j in range(0,m+10)] for i in range(0,n+10)]
    dp[0][0]=1
    for i in range(0,n+1):
        for j in range(1,m+1):
            dp[i][j]+=dp[i][j-1]
            if i>=j:
                dp[i][j]+=dp[i-j][j]
    print(dp[n][m])

糖果

由于在维护世界和平的事务中做出巨大贡献，Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。

在这一天，Dzx可以从糖果公司的 NN 件产品中任意选择若干件带回家享用。

糖果公司的 NN 件产品每件都包含数量不同的糖果。

Dzx希望他选择的产品包含的糖果总数是 KK 的整数倍，这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。

当然，在满足这一条件的基础上，糖果总数越多越好。

Dzx最多能带走多少糖果呢？

注意：Dzx只能将糖果公司的产品整件带走。

输入格式

第一行包含两个整数 NN 和 KK。

以下 NN 行每行 11 个整数，表示糖果公司该件产品中包含的糖果数目，不超过 10000001000000。

输出格式

符合要求的最多能达到的糖果总数，如果不能达到 KK 的倍数这一要求，输出 00。

数据范围

1≤N≤1001≤N≤100,
1≤K≤1001≤K≤100,

输入样例：

5 7
1
2
3
4
5

输出样例：

14

样例解释

Dzx的选择是2+3+4+5=14，这样糖果总数是7的倍数，并且是总数最多的选择。

IA=lambda:map(int,input().split())

n,m=IA()

a=[0 for i in range(0,n+1)]
dp=[[-1e18 for j in range(0,m+10)] for i in range(0,n+10)]
for i in range(1,n+1):
    a[i]=int(input())
dp[0][0]=0
for i in range(1,n+1):
    for j in range(0,m):
        dp[i][j]=max(dp[i-1][j],dp[i-1][(j+m-a[i]%m)%m]+a[i])

print(dp[n][0])

密码脱落

• 题目
• 提交记录
• 讨论
• 题解
• 视频讲解

X星球的考古学家发现了一批古代留下来的密码。

这些密码是由A、B、C、D 四种植物的种子串成的序列。

仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。

由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。

你的任务是：

给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。

输入格式

共一行，包含一个由大写字母ABCD构成的字符串，表示现在看到的密码串。

输出格式

输出一个整数，表示至少脱落了多少个种子。

数据范围

输入字符串长度不超过1000

输入样例1：

ABCBA

输出样例1：

0

输入样例2：

ABDCDCBABC

输出样例2：

3

区间dp

从当前样子变成初始状态需要添加叶子的数量 等价于 当前样子变成最大的回文串需要剪去的叶子的数量
即至少脱落多少个种子 等价于 总数量 - 最大回文子序列的长度

状态计算的选择方式和最长公共子序列类似

s=input()
n=len(s)

dp=[[0 for j in range(0,n+10)] for i in range(0,n+10)]

for le in range(1,n+1):
    for i in range(0,n):
        j=i+le-1
        if j>=n:break
        if le==1:
            dp[i][j]=1
        else:
            if s[i]==s[j]:
                dp[i][j]=dp[i+1][j-1]+2
            dp[i][j]=max(dp[i][j],dp[i+1][j])
            dp[i][j]=max(dp[i][j],dp[i][j-1])

print(n-dp[0][n-1])