动态规划第二课

tangguoyu · 2023-07-27 21:32:23 · 个人记录

例题1

题目描述：

题目分析

1.确定状态+转移方程

2.初始条件和边界状态

代码实现

#include<bits/stdc++.h>
using namespace std;
int f[114][114],a[114][114];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<m;++j)
        {
            if(a[i][j]==1)
            {
                f[i][j]=0;
                continue;
            }
            if(i==0&&j==0)
            {
                f[i][j]=1;
                continue;
            }
            f[i][j]=0;
            if(i>0)
            {
                f[i][j]+=f[i-1][j];
            }
            if(j>0)
            {
                f[i][j]+=f[i][j-1];
            }
        }
    }
    cout<<f[m-1][n-1];
    return 0;
}

例题2：paint house

题目描述：

有一排N栋房子，要把这些房子染成红，绿，蓝三种，相邻房子颜色不能相同，染成3种颜色的价格也不一样，问最少要花费多少

题目分析

1.确定状态

• 最后一步：

• 子问题

2.转移方程

f[i][0]=min{f[i-1][1]+cost[i-1][0],f[i-1][2]+cost[i-1][0]}

f[i][1]=min{f[i-1][0]+cost[i-1][0],f[i-1][2]+cost[i-1][0]}

f[i][2]=min{f[i-1][0]+cost[i-1][0],f[i-1][1]+cost[i-1][0]}

3.初始条件和边界状态

f[0][0]=f[0][1]=f[0][2]=0(不油漆任何房子的费用)

无边界状态

4.计算顺序

f[0][0],f[0][1],f[0][2]……f[n][0],f[n][1],f[n][2]

ans=min{f[n][0],f[n][1],f[n][2]}

小结：

例题3：decode ways

题目描述：

题目分析

1.确定状态

• 最后一步（最后一段）

• 子问题

2.转移方程

f[i]=f[i-1] (前i-1个数字)+f[i-2] (前i-2个数字)

3.初始条件和边界状态

初始条件：f[0]=1

边界状态：如果i=1,只看最后一个数字

4.计算顺序

f[0],……,f[n]

代码实现

#include<bits/stdc++.h>
using namespace std;
int f[114514];
int main()
{
    string s;
    cin>>s;
    int n=s.size();
    if(n==0)
    {
        cout<<1;
        return 0;
    }
    f[0]=1;
    int x;
    for(int i=1;i<=n;++i)
    {
        if(s[i-1]>='1'&&s[i-1]<='9')
        {
            f[i]+=f[i-1];
        }
        if(i>1)
        {
            x=10*(s[i-2]-'0')+s[i-1]-'0';
            if(s[i-2]!='0'&&x>=10&&x<=26)
            {
                f[i]+=f[i-2];
            }
        }
    }
    cout<<f[n];
    return 0;
}

坐标型动态规划

例题4：longest increasing continuous sussequence

题目描述：

题目分析

1.确定状态

• 最后一步

• 子问题

2.转移方程

f[j]=max{1,f[i-1]+1&&a[j-1]<a[j]}

3.初始条件和边界状态

无初始条件

边界状态：j>0,a[j]>a[j-1] f[0],……,f[n-1]

ans=min{f[0],……,f[n-1]}

代码实现