动态规划学习笔记（1）

记录一下慕课学习的笔记，以及例题代码

一。递归到动规的一般转化方法#

递归函数有 n 个参数就定义一个 n 维的数组，数组的下标是递归函数参数的取值范围。
这样就可以从边界值开始逐步填充数组，相当于计算递归函数值的逆过程。eg：例题 1 数字三角形

二。动规解题的一般思路#

1. 将原问题分解为子问题#

将原问题分解为若干个子问题，与原问题的形式相同或类似，只不过规模小了。
子问题都解决，原问题即解决。
子问题的解一旦求出就会被保存，所以每个子问题只要求解一次。

2. 确定状态#

状态：往往把和子问题相关的各个变量的一组取值称为一个状态。一个状态对应于一个或多个子问题。
值：所谓某个状态下的值就是这个状态所对应的子问题的解。
时间复杂度：整个问题的时间复杂度是状态数目乘以每个状态所需时间。
存储：若 K 个整型变量能够构成一个状态，且取值范围分别为 N1,N2,……,Nk，我们就可以用一个 K 维的数组 array [N1][N2]……[Nk] 来存储各个状态的 “值”，这个值未必是一个整数或浮点数，甚至可能是需要一个结构表示的，故 array 可以是一个结构数组。

3. 确定一些初始状态 (边界状态) 的值#

4. 确定状态转移方程#

定义出什么是状态，以及在该状态下的值后，就要找出不同的状态之间如何迁移。
即如何从一个或多个值已知的状态推出另一个状态的值("人人为我" 递推型)。状态的迁移可以用递推公式表示，此递推公式也可称作 "状态转移方程"。

三。能用动规解决的问题的特点#

1) 问题具有最优子结构性质#

最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，称其具有该性质。

2) 无后效性#

当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，与之前是采取哪种手段或经过哪条路径演变到当前这若干个状态无关。

四。例题#

例题 1. 数字三角形#

题意

: 给定一个由 n 行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。
对于给定的由 n 行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。
输入数据的第 1 行是数字三角形的行数 n，1≤n≤100。接下来 n 行是数字三角形各行中的数字。所有数字在 0..99 之间。
输出数据只有一个整数，表示计算出的最大值。

示例输入

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

示例输出

30

代码 1 记忆递归型动归程序

#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std;
//用递归的话会超时 重复计算太多
//所以将每次递归的结果算出来存到数组里
//叫做记忆递归型动归程序
int D[MAX][MAX];//D[r][j]表示第r行第j个数字(r,j从1开始算)
int maxSum[MAX][MAX];//从D(r,j)到底边的各条路径中，最佳路径的数字之和
int n;
int MaxSum(int i, int j) {
    if (maxSum[i][j] != -1)
        return maxSum[i][j];//若maxSum的值有被算过
    if (i == n) 
        maxSum[i][j] = D[i][j];
    else {
        int x = MaxSum(i+1, j);
        int y = MaxSum(i+1, j+1);
        maxSum[i][j] = max(x, y) + D[i][j];
    }
    return maxSum[i][j];
}
int main(){
    int i, j;
    cin >> n;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= i; j++) {
            cin >> D[i][j];
            maxSum[i][j] = -1;
        }
    }
    cout << MaxSum(1, 1) << endl;
    return 0;
}

代码 2 循环递推式动态规划

#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std;
//循环 递推式 动态规划
int D[MAX][MAX];//D[r][j]表示第r行第j个数字(r,j从1开始算)
int maxSum[MAX][MAX];//从D(r,j)到底边的各条路径中，最佳路径的数字之和
int n;
int main(){
    int i, j;
    cin >> n;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= i; j++) {
            cin >> D[i][j];
            maxSum[i][j] = -1;
        }
    }
    for (i = 1; i <= n; i++)
        maxSum[n][i] = D[n][i];
    for (i = n-1; i >= 1; i--) {
        for (j = 1; j <= i; j++) {
            maxSum[i][j] = 
                max(maxSum[i+1][j], maxSum[i+1][j+1]) + D[i][j];
        }
    }
    cout << maxSum[1][1] << endl;
    return 0;
}

例题 2. 神奇的口袋#

题意

有一个神奇的口袋，总的容积是 40，用这个口袋可以变出一些物品，这些物品的总体积必须是 40。John 现在有 n 个想要得到的物品，每个物品的体积分别是 a1，a2……an。John 可以从这些物品中选择一些，如果选出的物体的总体积是 40，那么利用这个神奇的口袋，John 就可以得到这些物品。现在的问题是，John 有多少种不同的选择物品的方式。

输入输出

输入:
3
20
20
20
输出:
3

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a[30]; int N;
int Ways[40][30];//Ways[i][j]表示从j种物品里凑出体积i的方法数
int main() {
    cin >> N;
    memset(Ways, 0, sizeof(Ways));
    for (int i = 1; i <= N; ++i) {
        cin >> a[i]; Ways[0][i] = 1;
    }
    Ways[0][0] = 1;
    for (int w = 1; w <= 40; w++) {
        for (int k = 1; k <= N; k++) {
            Ways[w][k] = Ways[w][k-1];
            if (w-a[k] >= 0)
                Ways[w][k] += Ways[w-a[k]][k-1];
        }
    }
    cout << Ways[40][N];
    return 0;
}

例题 3. 最长公共子序列#

题意

给出两个字符串求一个最长的公共子序列的长度

输入输出

输入:
abcfbc abfcab
programming contest
abcd mnp
输出:
4
2
0

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[1001][1001];
/*思路:设dp(i,j)表示s1左边i个字符形成的子串
与s2左边j个字符形成的字串的最长公共子序列的长度
dp(n,0) = 0, dp(0,n) = 0; 
if (s1[i-1] == s2[j-1]) dp(i,j) = dp(i-1,j-1) + 1;
else dp(i, j) = max(dp(i,j-1), dp(i-1,j));*/
int main() {
    string s1, s2;
    cin >> s1 >> s2;
    int len1 = s1.length();
    int len2 = s2.length();
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <=len2; j++) {
            if(s1[i-1] == s2[j-1]) 
                dp[i][j] = dp[i-1][j-1] + 1;
            else 
                dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
        }
    }
    cout << dp[len1][len2] << endl;
    return 0;
}

例题 4. 最长上升子序列#

题意

输入第一行序列的长度 N，第二行 N 个整数
输出最长上升子序列的长度

输入输出

输入样例:
7
1 7 3 5 9 4 8
输出样例:
4

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
/*思路:分解为求以ak为终点的最长上升子序列的长度 ，maxLen(k)表示以ak为终点的最长上升子序列长度
为在ak左边 且ai小于ak 长度最大的最长上升子序列的长度+1
因为ak左边任何终值小于ak的子序列加上ak后就能形成一个更长的上升子序列*/
int a[maxn]; int maxLen[maxn];
int main() {
    int N, ans = -1;  cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> a[i]; maxLen[i] = 1;
    }
    for (int i = 2; i <= N; i++) {
        //每次求以第i个数为终点的最长上升子序列的长度
        for(int j = 1; j < i; j++) {
            //以第j个数为终点的最长上升子序列
            if (a[j] < a[i]) {
                maxLen[i] = max(maxLen[i], maxLen[j]+1);
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        if(maxLen[i] > ans) ans = maxLen[i];
    }
    cout << ans << endl;
    return 0;
}
//时间复杂度O(N^2)

转自慕课程序设计与算法（二）动态规划 ppt