算法10 动态规划DP入门

bigbigli
基础算法
2024-06-11
800热度
0评论

动态规划法

动态规划是一种处理问题的算法思想，这些问题主要有以下特征：

多段决策

问题可以按时间顺序分解成若干相互联系的阶段，在每个阶段都需要做出决策。

最优子结构

我们可以把当前的问题分解成若干个规模更小的子问题，当前问题的最优解，可以由子问题的最优解得到。

无后效性

某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响。

动态规划方法将问题分解为一组更简单的子问题，在求解每个子问题时，会将子问题的解保存起来，在后面遇到相同的子问题时避免重复计算，利用空间换时间。

递归生成斐波那契数列

递归虽然能求出斐波那契数列的第n项，但时间复杂度极高，比如我们要求fib(5)，就必须先求出fib(4)和fib(3)，求fib(4)时还需要再调用一次fib(3)，这里fib(3)就需要再求一次，我们会发现有很多值需要多次计算。

比如要求fib(n)时，需要将f(0)和f(1)重复调用很多次。

通过记忆化存储优化程序

我们可以在计算的过程中，将fib(n)的结果保存到F[n]数组中去，借此避免重复计算，这种思路就是基于动态规划的基本结构。

#include <iostream>
using namespace std;
int dp[110];
int fib(int n)
{
    if(n==0||n==1) return dp[n]=1; //将1记忆在F[n]中并返回
    if(dp[n]) return dp[n]; //如果计算完毕则返回
    return dp[n] = fib(n-2)+fib(n-1);
}

int main(){
    int n;
    cin >> n;
    cout << fib(n);
    return 0;
}

通过动态规划优化程序

#include <iostream>
using namespace std;
int F[110];
int main()
{
    int n;
    cin >> n;
    F[0] = 1;
    F[1] = 1;
    for(int i=2;i<=n;i++) F[i] = F[i-2]+F[i-1];
    cout << F[n];
    return 0;
}

这个算法会从小到大计算斐波那契数列，所以计算F[i]时，在此之前就已经完成了F[i-1]和F[i-2]的计算。

数字三角形

观察下面的数字三角形。写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大，为30。

解析

1.先确定问题中的状态。(通常用变量表示)

2.从最后一步出发，找到相邻两个状态的关系,如何从状态 n-1 到状态n。(状态转移方程)

3.找到问题的边界。(通常是起始状态的初始值)

4.编写代码求解。(递归或者迭代)

参考程序

#include<bits/stdc++.h>
using namespace std;
int a[1001][1001];
int dp[1001][1001],ans;
//dp[i][j]表示从第n行到a[i][j]的最大值
//dp[i][j]可以由dp[i+1][j],dp[i+1][j+1]的值推出
//dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1])
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++) cin>>a[i][j];
    for(int i=1;i<=n;i++)dp[n][i]=a[n][i];
    //初始化边界条件
    for(int i=n-1;i>=1;i--) //从第n-1行开始
        for(int j=1;j<=i;j++) dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
    cout<<dp[1][1];
    return 0;
}

最长上升子序列

给定一整型数列{a1,a2…,an}（0<n<=500），找出最长上升子序列，并求出其长度。

如：1 9 10 5 11 2 13的最长上升子序列是1 9 10 11 13，长度为5。

【输入描述】第一行输入一个整数n，第二行输入n个整数

【输出描述】输出最长的上升子序的长度

【输入样例】

7
1 9 10 5 11 2 13

【输出样例】5

参考程序

#include<bits/stdc++.h>
using namespace std;
int a[505],dp[505];
//dp[i]表示前i项中包含第i项的最长子序列
//初始状态dp[i]=1;
//dp[i]=max(dp[i],dp[j]+1)
//包含第i项的最长子序列，可以由前面的j(1~i-1)项的最长子序列得出，
//如果a[j]<a[i], dp[i]=max(dp[i],dp[j]+1)
int main()
{
    int t,n,mx;
    cin>>n;
    mx=1;
    //边界初始化
    for(int i=1;i<=n;i++){
        cin>>a[i];
        dp[i]=1;
    }
    for(int i=1;i<=n;i++)
    {
        //从1~i-1项去找
        for(int j=1;j<i;j++)
        {
            //如果a[j]<a[i],则说明a[i]可以连接在a[j]后
            if(a[i]>a[j])
            {
                //此时dp[i]可能会变长
                dp[i]=max(dp[i],dp[j]+1);
                mx=max(dp[i],mx);
            }
        }
    }
    cout<<mx<<endl;
    return 0;
}