[数据结构与算法]动态规划一

动态规划总论:状态设计的要点和技巧

再探:零钱兑换问题

零钱兑换
https://leetcode.cn/problems/coin-change/
给一个硬币面额的可选集合coins，求拼成金额amount最少需要多少枚硬币。
例: coins = [20,10,5,1],amount = 46
答案:46= 20+ 20+5+1

零钱兑换:搜索

状态:剩余金额、已用硬币枚数

零钱兑换:最优子结构

状态中没有必要包含“已用硬币枚数”
对于每个“剩余金额”，搜一次，求出“兑换这个金额所需的最少硬币枚数”就足够了

原始状态:剩余金额、已用硬币枚数，目标:到达终点(O元)
新状态:剩余金额，最优化目标:硬币枚数最少
推导关系:“兑换n元的最少硬币枚数”
opt(n)= min(opt(n - 1), opt(n - 9), opt(n- 10))+1
状态＋最优化目标＋最优化目标之间具有递推关系=最优子结构

零钱兑换:最优子结构

零钱兑换: 递推实现

class Solution {
    public int coinChange(int[] coins, int amount) {
        int INF = (int)1e9;
        int[] opt = new int[amount + 1];
        opt[0] = 0;
        for(int i = 1; i <= amount; i++) {
            opt[i] = INF;
            for(int j = 0;j < coins.length; j++){
                if(i - coins[j] >= 0)
                    opt[i] = Math.min(opt[i], opt[i - coins[j]] + 1);
            }
        }
        if(opt[amount] >= INF) opt[amount] = -1;
        return opt[amount];
    }
}

零钱兑换: 记忆化搜索

class Solution {
    vector<int>count;
    int dp(vector<int>& coins, int rem) {
        if (rem < 0) return -1;
        if (rem == 0) return 0;
        if (count[rem - 1] != 0) return count[rem - 1];
        int Min = INT_MAX;
        for (int coin:coins) {
            int res = dp(coins, rem - coin);
            if (res >= 0 && res < Min) {
                Min = res + 1;
            }
        }
        count[rem - 1] = Min == INT_MAX ? -1 : Min;
        return count[rem - 1];
    }
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount < 1) return 0;
        count.resize(amount);
        return dp(coins, amount);
    }
};

无论是递推实现还是记忆化搜索（递归实现)
这种定义状态＋最优子结构＋推导关系的解题方法
其实就是动态规划算法

简单的线性动态规划

**动态规划(DP, dynamic programming)**是一种对问题的状态空间进行分阶段、有顺序、不重复、决策性遍历的算法
动态规划的关键与前提:
重叠子问题——与递归、分治等一样，要具有同类子问题，用若干维状态表示最优子结构——状态对应着一个最优化目标，并且最优化目标之间具有推导关系无后效性——问题的状态空间是一张有向无环图（可按一定的顺序遍历求解)

动态规划一般采用递推的方式实现
也可以写成递归或搜索的形式，因为每个状态只遍历一次，也被称为记忆化搜索
动态规划三要素:阶段、状态、决策

一道动态规划题目的标准题解:
设opt[i]表示凑成金额 i 所需的最少硬币数
状态转移方程

边界

目标

时间复杂度

一道动态规划题目，写出状态转移方程，就已经完成了大半的工作
剩下的任务就是照着方程写几个循环递推实现就行了

实战

63.不同路径Ⅱ
https://leetcode.cn/problems/unique-paths-ii/

一个机器人位于一个m x n网格的左上角
机器人每次只能向下或者向右移动一步机
器人试图达到网格的右下角
现在考虑网格中有障碍物
那么从左上角到右下角将会有多少条不同的路径?

Bottom-up
f[i,j]表示从(i,j)到End的路径数
如果(i,j)是空地，fli,j]= f[i＋1,j+f Li,j＋1]
否则f[ti,j= 0
Top-down
f[,j]表示从Start到(i,j)的路径数
如果i,j)是空地，f Li,j]= f[i-1,j]+ f li,j-1]
否则ft,j]= 0

Bottom-up记忆化搜索（递归、分治思想)

int countPaths(boolean[][ ]grid，int row，int col) {
	if ( !validSquare(grid，row,col)) return 0;
	if (isAtEnd(grid，row，col)) return 1;
	return countPaths(grid，row + 1，col) + countPaths(grid，row，col + 1);
}

1143.最长公共子序列
https://leetcode.cn/problems/longest-common-subsequence/

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {

        int n=text1.size();
        int m=text2.size();

        vector<vector<int>> dp(n+1,vector<int>(m+1,0));

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(text1[i-1]==text2[j-1])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                }else
                {
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[n][m];
    }
};

给两个字符串，求最长公共子序列(LCS)，例如:
text1 = “abcde”
text2 = “ace”

入手DP问题第一步:人工模拟的话怎么算?
拿一个小例子，画个表

确定“状态”的原则:
寻找变化信息

• abcd, ac (ac)=>abcde, ace (ace)
• 两个子串的长度是变化的，内容是固定的

确定“最优子结构”的原则: 寻找代表

• 同样的两个子串，能组成很多公共子序列
• 只关心最大长度，不关心具体长什么样

确定“阶段”的原则:线性增长的轮廓

• “轮廓”是已计算区域与未计算区域的分界

确定“决策”的原则:人工模拟时考虑了哪些选项?

f[i, j] 表示text1的前i 个字符和text2 的前j个字符能组成的LCS的长度

如果text1[i]=text2[j]: f[i, j]= f[i-1,j-1]+1
如果text1[i]≠text2[j]: f[i, j]= max(f [i一1,j],f [i,j一1])

动规题目的边界处理技巧
方法一:
f[0,0]=0，然后递推时用if语句判断，目标f [n - 1,m -1]
方法二:
认为字符串下标从1开始，f[i,0]=0与f[0,j]=0均作为边界，目标f[n, m]

300.最长递增子序列
https://leetcode.cn/problems/longest-increasing-subsequence/

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int f[] = new int[n];
        int pre[] = new int[n];
        for(int i = 0; i < n; i++) {
            f[i] = 1;
            pre[i] = -1;
        }
        for(int i = 1; i < n; i++)
            for(int j = 0; j < i; j++)
                if(nums[j] < nums[i] && f[i] < f[j] + 1){
                    f[i] = f[j] + 1;
                    pre[i] = j;
                }
        int ans = 0;
        int end = -1;
        for(int i = 0; i < n; i++)
            if(f[i] > ans) {
                ans = f[i];
                end = i;
            }
        print(nums, pre, end);
        return ans;
    }

    void print(int[] nums, int[] pre, int i){
        if(pre[i] != -1) print(nums, pre, pre[i]);
        System.out.println(nums[i]);
    }
}

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {

        int n=nums.size();

        vector<int> dp(n,1);
        int max_k=1;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j]){
                    dp[i]=max(dp[j]+1,dp[i]);
                    max_k=max(max_k,dp[i]);
                }
            }
        }



        return max_k;
    }        
};

动态规划解题步骤

动态规划“轮廓变化”

动态规划打印方案

动态规划题目打印方案的原则:记录转移路径＋递归输出
动态规划选取“代表”，维护了一个最优子结构
如果记录每个最优子结构的详细方案，时间复杂度会上升
以LCS为例，本来是0(len2)，每个opt[i,j]记录一个方案（字符串），就变成了0(len3)

正确做法:
记录每个f[i,j]是从哪里转移过来的(f[i-1,j]，fLi,j-1]还是f[i一1,j一1])
整个动规完成，求出f [n,m]后，再从(n,m)开始递归复原最优路径

53.最大子数组和
https://leetcode.cn/problems/maximum-subarray/

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // int pre = 0, maxAns = nums[0];
        // for (const auto &x: nums) {
        //     pre = max(pre + x, x);
        //     maxAns = max(maxAns, pre);
        // }
        // return maxAns;
        
        int n=nums.size();

        vector<int> dp(n+1,0);
        dp[0]=nums[0];
        int mmax=dp[0];

        for(int i=1;i<n;i++)
        {
            dp[i]=max(nums[i],dp[i-1]+nums[i]);
            mmax=max(mmax,dp[i]);
        }
        
        return mmax;
    }
};

f[i]表示以i为结尾的最大子序和
f[i]=max(f [i -1]+mums[i], nums[i])

状态中何时需要“包含结尾”?
–当结尾参与判定条件时，例如LIS中a[j]<a[i]，此处子序和要“连续”

152.乘积最大子数组
https://leetcode.cn/problems/maximum-product-subarray/

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector <int> maxF(nums), minF(nums);
        for (int i = 1; i < nums.size(); ++i) {
            maxF[i] = max(maxF[i - 1] * nums[i], max(nums[i], minF[i - 1] * nums[i]));
            minF[i] = min(minF[i - 1] * nums[i], min(nums[i], maxF[i - 1] * nums[i]));
        }
        return *max_element(maxF.begin(), maxF.end());
    }
};

70.爬楼梯
https://leetcode.cn/problems/climbing-stairs/description/

class Solution {
public:
    int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};

120.三角形最小路径和
https://leetcode.cn/problems/triangle/description/

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> f(n, vector<int>(n));
        f[0][0] = triangle[0][0];
        for (int i = 1; i < n; ++i) {
            f[i][0] = f[i - 1][0] + triangle[i][0];
            for (int j = 1; j < i; ++j) {
                f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];
            }
            f[i][i] = f[i - 1][i - 1] + triangle[i][i];
        }
        return *min_element(f[n - 1].begin(), f[n - 1].end());
    }
};

673.最长递增子序列的个数
https://leetcode.cn/problems/number-of-longest-increasing-subsequence/

class Solution {
    int binarySearch(int n, function<bool(int)> f) {
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) / 2;
            if (f(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

public:
    int findNumberOfLIS(vector<int> &nums) {
        vector<vector<int>> d, cnt;
        for (int v : nums) {
            int i = binarySearch(d.size(), [&](int i) { return d[i].back() >= v; });
            int c = 1;
            if (i > 0) {
                int k = binarySearch(d[i - 1].size(), [&](int k) { return d[i - 1][k] < v; });
                c = cnt[i - 1].back() - cnt[i - 1][k];
            }
            if (i == d.size()) {
                d.push_back({v});
                cnt.push_back({0, c});
            } else {
                d[i].push_back(v);
                cnt[i].push_back(cnt[i].back() + c);
            }
        }
        return cnt.back().back();
    }
};

https://ke.qq.com/course/417774?flowToken=1041943