算法笔记之初识DP（一）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法笔记之初识DP（一），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4112字，纯文字阅读大概需要6分钟。

内容图文

动态规划（DP）不是某种具体算法，而是一种思想。把大问题转化为小问题，利用小问题的解推断出大问题就是DP的核心思想。

• step 1: 设计状态。把面临的每一个问题，用状态表达出来。
• step 2: 设计转移。写出状态转移方程，从而利用小问题的解推出大问题的解。

两种状态转移的方法

• 1.pull型：从哪来， 从0到n
• 2.push型：到哪去， 从n到0

e.g.上楼梯问题
pull: f[n] = f[n-1] + f[n-2];
push: f[n] -> f[n+1] += f[n]
f[n+2] += f[n]

push能用到f[0]的信息，可能会好下手

1.暴力枚举 与 记忆化

暴力枚举保存了“每一步采取什么操作”的信息，其为指数级复杂度， 且对重复进行递归，浪费性能

70.Climbing Stairs

• 想知道的信息
  从 0 级走到 n 级的方案数 f(n).
• 为了得到f(n)，我们需要什么信息
  知道 f(n) 和 f(n ? 1) 即可。

只需要f[1] 和 f[2]

暴力模拟，很多重复的步骤， 比如climbStairs(n)出现很多次，没意义。

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

需要一种更好的算法，比如保留信息f[x]来表示从0级走到x级的方案数，假设f[1], f[2], .., f[n-1]已知，很容易退出下一步。
pull

class Solution {
public:
    int memo[46] = {0};
    int climbStairs(int n) {
        if (n == 1) return 1;
        else if (n == 2) return 2;
        memo[1] = 1; memo[2] = 2;
        for (int i = 3; i<=n; i++) {
            memo[i] = memo[i-1] + memo[i-2];
        }
        return memo[n];
    }
};

push

class Solution {
public:
    int memo[47] = {0};
    int climbStairs(int n) {
        memo[0] = 1;
        for (int i=0; i<n; i++) {
            memo[i+1] += memo[i];
            memo[i+2] += memo[i];
        }
        return memo[n];
    }
};

322. Coin Change

• 想知道的信息
  凑到n块钱所需的最少硬币数f(n).
• 为了得到f(n)，我们需要什么信息
  知道 f(n-1) 和 f(n?5) 即可。（当硬币类型位1,5时）

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {    
        vector<int> memo(amount+1, 0x7ffffff0);
        // push
        memo[0] = 0;
        for (int i=0; i<=amount; i++ ) {
            for (int j=0; j<coins.size(); j++) {
                if (coins[j]  <= amount - i) {
                    memo[i+coins[j]] = min(memo[i+coins[j]], memo[i]+1);
                }
            }
        }
        return memo[amount] != 0x7ffffff0? memo[amount] : -1;
    }
};

优化版->按币的值来跳 + greedy

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int res = INT_MAX, n = coins.size();
        sort(coins.begin(), coins.end());
        helper(coins, n - 1, amount, 0, res);
        return (res == INT_MAX) ? -1 : res;
    }
    void helper(vector<int>& coins, int start, int target, int cur, int& res) {
        if (start < 0) return;
        if (target % coins[start] == 0) {
            res = min(res, cur + target / coins[start]);
            return;
        }
        for (int i = target / coins[start]; i >= 0; --i) {
            if (cur + i >= res - 1) break;
            helper(coins, start - 1, target - i * coins[start], cur + i, res);
        }
    }
};

狗屁不通生成器

300. Longest Increasing Subsequence

f[x] 表达的是“以 a[x] 结尾的最长的上升子序列长度”。

push

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        vector<int> memo(nums.size(), 1);

        for (int i=1; i<nums.size(); i++) {
            for (int j=0; j<i; j++) {
                if (nums[i] > nums[j] && memo[i] < memo[j]+1) {
                    memo[i] = memo[j]+1;
                }
            }
        }
        return *max_element(memo.begin(), memo.end());
    }
};

二分

iterator lower_bound( const key_type &key ): 返回一个迭代器，指向键值>= key的第一个元素。
iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值> key的第一个元素。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int>vec;
        for(auto n:nums){
            // lower_bound 用来找是哪个pile， 不存在比n大的情况，lower_bound返回vec.end(), 加入新的pile，所以有多少pile就有多大
            auto it = lower_bound(vec.begin(),vec.end(),n);
            if(it!=vec.end()){
                *it=n;
            }else{
                vec.push_back(n);
            }
        }
        return vec.size();
    }
};

https://www.youtube.com/watch?v=22s1xxRvy28&feature=youtu.be

1143. Longest Common Subsequence

记 f(x, y) 表示 A 的前 x 个元素，与 B 的前 y 个元素的 LCS

• f(n, m) 可以是 f(n ? 1, m) -> a[n] != b[m]
• f(n, m) 可以是 f(n, m ? 1) -> a[n] != b[m]
  如果 a[n] = b[m]，则 f(n, m) 可以取 f(n ? 1, m ? 1) + 1

push

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> memo (text1.size()+1, vector<int> (text2.size()+1));
        
        // f(x,y)
        // f(x+1,y)
        for (int i=0; i<text1.size(); i++) {
            for (int j=0; j<text2.size(); j++) {
                if (text1[i] == text2[j]) memo[i+1][j+1] = memo[i][j]+1;
                else {
                    memo[i+1][j+1] = max(memo[i][j+1], memo[i+1][j]);
                }
            }
        }
        return memo[text1.size()][text2.size()];
    }
};

P1464.Function

记忆化搜索模板题

内容总结

以上是互联网集市为您收集整理的算法笔记之初识DP（一）全部内容，希望文章能够帮你解决算法笔记之初识DP（一）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---