动态规划

https://blog.csdn.net/zw6161080123/article/details/80639932
动态规划：最关键是定义子问题f(n)，并且找出当前问题和子问题之间的关系{f(n), f(n-1), arr[n]} 之间的关系。
定义子问题，是找出子问题关系的关键点。

1. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
思路：
1.定义子问题：定义dp[i]为前[0-i] 个元素，以第i个元素结尾的最长上升子序列元素的长度。
备注：一维数组，自底向上的场景。

int lengthOfLIS(vector<int>& nums) {
    if (nums.size() <= 1) {
        return nums.size();
    }
    vector<int> result(nums.size(), 1);

    for (int i = 1; i < nums.size(); i++) {
        auto cur = nums[i];
        for (int j = 0; j < i; j++) {
            if (cur > nums[j] && (result[j] + 1 > result[i])) {
                result[i] = result[j] + 1;
            }
        }
    }
    std::sort(result.begin(), result.end());

    return result.back();
}

2.最大子序列和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
思路：
1.定义子问题：定义dp[i]为前[o-i]个元素中，以第i个元素作为结尾连续子数组最大和。
2.根据子问题定义：如果result[i-1] > 0: result[i] = result[i-1] + cur; 否则：result[i] = cur;
备注：一维数组，自底向上的场景。

int maxSubArray(vector<int>& nums) {
    vector<int> result(nums.size(), 0);
    result[0] = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        auto cur = nums[i];
        if (result[i-1] > 0) {
            result[i] = result[i-1] + cur;
        } else {
            result[i] = cur;
        }
    }

    std::sort(result.begin(), result.end());
    cout << "max value:" << result.back() << endl;
    return result.back();
}

3.数字塔从上到下路径中和最大的路径
数字塔是第i行有i个数字组成，从上往下每个数字只能走到他正下方数字或者正右方数字，求数字塔从上到下所有路径中和最大的路径.
思路：
1.定义子问题：dp[i][j]为以arr[i][j]结尾的，最大路径和的值。
2.根据题目描述：写递推关系。
备注：这是二维数组的自底向上的场景。

int minNumberInRotateArray(const vector<vector<int>>& arr) {
    int max = 0;
    vector<vector<int>> result;
    result[0][0] = arr[0][0];
    for (int i = 1; i < arr.size(); i++) {
        for (int j = 0; j < arr[i].size(); j++) {
            if (j == 0) {
                result[i][j] = arr[i-1][j] + arr[i][j];
            } else {
                result[i][j] = std::max(result[i-1][j], result[i-1][j]) + arr[i][j];
            }
            
            max = std::max(max, result[i][j]);
        }
    }
    
    return max;
}

4.背包问题

问题：在N件物品取出若干件放在容量为W的背包里，每件物品的体积为W1，W2……Wn（Wi为整数），与之相对应的价值为P1,P2……Pn（Pi为整数），求背包能够容纳的最大价值。
思路：
像这种固定数值的组合问题，比如这个问题的W总容量，跟下个实例零钱问题的总钱数，都是适合用动态规划来解决的问题

public static int PackageHelper(int n,int w[],int p[],int v) {
  //设置一个二维数组:1) 横坐标代表从第一个物品开始放到第几个物品 2) 纵坐标代表背包还有多少容量. 3) dp代表最大价值
        int dp[][] = new int[n+1][v+1];
        for(int i=1;i<n+1;i++){
            //价值按照连续的处理，应为j-w[i]:可能是某一个数。按连续计算可能有冗余，但是最终都是为了算dp[n][v]
            for(int j=1;j<=v; j++){
                if(j>=w[i]){
                    /*
                     * 当能放得下这个物品时，放下这个物品，价值增加，但是空间减小，最大价值是dp[i-1][j-w[i]]+p[i]
                     * 当不放这个物品时，空间大，物品还是到i-1，最大价值是dp[i-1][j]
                     * 比较这两个大小，取最大的，就是dp[i][j]
                     */
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]]+p[i]);
                }else{
                    //如果放不下，就是放上一个物品时的dp
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][v];
}