算法笔记--动态规划

动态规划的递归写法

动态规划要记录子问题的解，避免下次遇到相同的子问题时的重复计算

在计算斐波那契数列时，我们采用递归的写法：

int F(int n){
    if(n == 0 || n == 1) return 1;
    else return F(n - 1) + F(n - 2);
}

这时候会涉及很多重复计算，如当n==5时，计算F(5) = F(4) + F(3)，在接下来计算F(4) = F(3) + F(2)时，有重复计算了F(3)。

为了避免重复计算，引入dp数组，用来保存已经计算过的结果，当dp[n]=-1表示F(n)还没有被计算

int dp[MAXN] = {-1};

int F(int n){
    if(n == 1 || n == 0) return 1;			// 递归边界
    if(dp[n] != -1) return dp[n];			// 已经计算的直接返回
    else{									
        dp[n] = F(n - 1) + F(n - 2);		// 计算F(n)保存到dp[n]
        return dp[n];						// 返回F(n)的结果
    }
}

通过记录计算过的内容，在下次使用是便不需要重复计算，这就是记忆化搜索

动态规划的适用于一个问题必须有重叠子问题

动态规划的递推写法

对于数塔问题，如果开一个二维数组f，其中f[i][j]存放第i层的第j个数字，那么有f[1][1]=5,

f[2][1] = 8，f[2][2] = 3...，求最后将路径上所有数字相加后得到的和最大是多少

Snipaste_2020-04-24_11-26-40

如果每次从头遍历，那会有很多重复的访问，通过动态规划，列出状态转移方程

Snipaste_2020-04-24_11-29-31

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1000;
int f[maxn][maxn], dp[maxn][maxn];
int main(){
    int n; 
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        for(int j = 1;  j <= i; j++){
            scanf("%d", &f[i][j]);
        }
    }
    // 边界
	for(int j = 1; j <= n; j++){
        dp[n][j] = f[n][j];
    }
    // 从n-1层不断往上计算出dp[i][j]
    for(int i = n - 1; i >= 1; i--){
        for(int j = 1; j <= i; j++){
            dp[i][j] = dp[i + 1][j] + d[i + 1][j + 1] + f[i][j];
        }
    }
    printf("%d
", dp[1][1]);		// dp[1][1]为所要答案
 	return 0;
}

最大连续子序列

Snipaste_2020-04-24_11-41-15

Snipaste_2020-04-24_11-45-01

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 10010;
int A[maxn], dp[maxn];
int main(){
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &A[i]);
    }
    // 边界
    dp[0] = A[0];
    for(int i = 1; i < n; i++){
        dp[i] = max(A[i], dp[i-1] + A[i]);	// 状态转移方程
    }	
    int k = 0;
    for(int i = 1; i < n; i++){
        if(dp[i] > dp[k])
            k = i;
    }
    printf("%d", dp[k]);
    return 0;
}