Noname's Blog
信息安全专业的小萌新,立志走上更大的舞台
动态规划刷题记录

动态规划

Updating...

思路:对每个子问题的解决方法都做出选择,并且会一直保持以前的运算,并根据以前的结果对当前进行选 择,可以回退

最优子结构:opt[n] = best_of(opt[n-1], opt[n-2], ...)

存储中间状态:opt[i]

DP方程:
Fib: opt[i] = opt[n-1]+opt[n-2]

二维路径:opt[i,j] = opt[i+1][j]+opt[i][j+1] 且判断a[i][j]是否空地
if a[i,j] = '空地':
	opt[i,j] = opt[i+1, j] + opt[i, j+1]
else:
	opt[i,j] = 0

斐波那契数列

1.普通写法

指数级的复杂度,会超时

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

代码简化后

int fib(int n){
	return n <= 1? n : fib(n-1)+fib(n-2);
}

2.记忆化搜索

增加一个存储已经计算过的内容的数组

int fib(int n, int[] memo){
	// 递归终止条件
    if(n <= 1){
		return n;
    }
    // 该值没有被计算过
    if(memo[n] == 0){
        memo[n] = fib(n-1) + fib(n-2);
    }
    // 下探一层
    return memo[n];
}

3.自底向上迭代处理

0,1,1,2,3,5,8,13

int fib(int n)
{
    int f = 0, g = 1;// fib(0), fib(1)
    for(int i = 2; i < n; i++){
        g = g + f;//1,
        f = g - f;//1
    }
    return g;
}
int array[n] = {0};
array[1] = 1;
for (int i = 2; i <= n; i++)
    array[i] = array[i-1] + array[i-2];

return array[n];

爬楼梯

https://leetcode-cn.com/problems/climbing-stairs/submissions/

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。

1.  1 阶 + 1 阶
2.  2 阶
    示例 2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。

1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

归纳分析

n=1, 1
n=2, 1+1, 2
n=3, 1+1+1, 1+2, 2+1
..
所以在第4层的时候就可以考虑3+1, 2+2, 即n-1和n-2的情况

超时写法

class Solution {
public:
    int climbStairs(int n) {
        //input
        if(n == 1 || n == 0){
            return 1;
        }else if(n == 2){
            return 2;
        }else{
            return climbStairs(n-1)+climbStairs(n-2);
        }
    }
};

记忆化

class Solution {
public:
    vector<int> memo = vector<int>(100, 0); //新的一种创建方式
    //int memo[100] = {0}; 
    //不可以在递归里面新建,会超时
    int climbStairs(int n) {
        // 递归终止条件
        if(n <= 3) return n;
        // 判断该值是否被计算过
        if(memo[n] == 0){
            memo[n] = climbStairs(n-1) + climbStairs(n-2);
        }
        return memo[n];
    }
};

自底向上

class Solution {
public:
    int dp[100] = {0};
    int climbStairs(int n) {
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n;++i){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};
class Solution {
public:
    int climbStairs(int n) {
        int f = 0, g = 1;
        while(0 < n--){
            g = g + f;
            f = g - f;
        }
        return g;
    }
};

最长公共子序列

https://leetcode-cn.com/problems/longest-common-subsequence/

给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

 
示例 1:

输入:text1 = "abcde", text2 = "ace" 
输出:3  
解释:最长公共子序列是 "ace" ,它的长度为 3 。
示例 2:

输入:text1 = "abc", text2 = "abc"
输出:3
解释:最长公共子序列是 "abc" ,它的长度为 3 。
示例 3:

输入:text1 = "abc", text2 = "def"
输出:0
解释:两个字符串没有公共子序列,返回 0 。
 
提示:
1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

画个举例的格子:

FOSH vs FORTFOSH vs FISH

左图:

text1[1][1]==text2[1][1] 所以有 dp[1][1]=dp[0][0]+1

text1[2][2]!=text2[2][2]则取上下的最大值,即dp[2][2]=max(dp[1][2], dp[2][1])

整理状态方程得:

if(text1[i][j] == text2[i][j]){
	dp[i][j] = dp[i-1][j-1] + 1;
}else{
    dp[i][j]=max(dp[i][j-1], dp[i-1][j]);
}

右图类似

1.png

记录创建二维数组的新法子:

vector<vector<int>> dp(len1 + 1,vector<int>(len2 + 1, 0));

一个小坑,也是一开始思路不清晰的地方:

循环从1起,即判断text1[i-1]与text2[j-1]

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int len1 = text1.size();
        int len2 = text2.size();
        vector<vector<int>> dp(len1 + 1,vector<int>(len2 + 1, 0));
        for(int i = 1; i <= len1 ; i++){
            for(int j = 1; j <= len2; j++){
                if(text1[i-1] == text2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        return dp[len1][len2];
    }
};

最大子序和

https://leetcode-cn.com/problems/maximum-subarray/

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

 
示例 1:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:

输入:nums = [1]
输出:1
示例 3:

输入:nums = [0]
输出:0
示例 4:

输入:nums = [-1]
输出:-1
示例 5:

输入:nums = [-100000]
输出:-100000
 

提示:

1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105
 
进阶:如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的 分治法 求解。

假设结果存于dp[i]中存储目前最大的和

在扫描num数组时

dp[i-1]<0nums[i]>0, dp[i]=nums[i]

dp[i-1]>0, 要对比nums[i]和

dp方程:

dp[i] = nums[i]
dp[i] = max(nums[i], dp[i-1]+nums[i])
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        vector<int> dp = vector<int>(len+1, 0);

        if(len == 1){
            return nums[0];
        }

        dp[0] = nums[0];
        
        for(int i = 1;i < len;i++){
            if(dp[i-1] < 0){
                dp[i] = nums[i];
            }else{
                dp[i] = max(nums[i], dp[i-1] + nums[i]);
            }
        }
        int ret = dp[0];
        for(int i = 1; i < len;i++){
            ret = max(dp[i], ret);
            printf("%d ", ret);
        }
        
        return ret;
    }
};