算法刷题-动态规划2

珠宝的最高价值

题目

大佬思路
多开一行使得代码更加的简洁

移动到右侧和下侧
dp[ i ][ j ]有两种情况：
第一种是从上面来的礼物最大价值：dp[ i ][ j ] = dp[ i – 1 ][ j ] + g[ i ][ j ]
第二种是从左面来的礼物最大价值：dp[ i ][ j ] = dp[ i ][ j – 1 ] + g[ i ][ j ]
所以得出状态表达式，dp[ i ][ j ] = max( dp[ i ][ j – 1 ]，dp[ i – 1 ][ j ] ) + g[ i ][ j ]
2。为了简洁代码，多增加一行

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        //dp[i][j]表示从grid[0][0]到grid[i - 1][j - 1]时的最大价值
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
}

class Solution { 
public: 
    int maxValue(vector<vector<int>>&amp; grid) { 
        int m = grid.size(), n = grid[0].size(); 
        vector<vector<int>> dp(m + 1, vector<int>(n + 1)); 
        for (int i = 1; i <= m; i++) { 
            for (int j = 1; j <= n; j++) { 
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];

            }
        }
        return  dp[m][n]; 
    }
};

下降路径最小和

头文件： #include< algorithm >
返回值： 两个函数返回的都是迭代器，所以要提取数值的话需要在函数前加上*
语法格式： max_element(first,end,cmp);其中cmp为可选择参数（自定义排序可用，默认不需要填）
两个函数默认都是从小到大排列， max_element() 输出最后一个值， min_element() 输出第一个值。
这里要特别注意：如果自定义排序是从大到小的， max_element() 和min_element() 的返回结果相反，也就是说max_element()返回的是最小值，min_element()返回的是最大值 。

• 定义函数dp[i][j] ，是关于路径到达 i,j 点的最小值
• 然后找 关系式，分析最后一点是从哪里得到的， 从左上方来：dp[ i – 1 ][ j – 1 ] + m[ i ][ j ]，从正上方来：dp[ i – 1 ][ j ] + m[ i ][ j ]， 从右上方来：dp[ i – 1 ][ j + 1 ] + m[ i ][ j ]

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>&amp; matrix) {
        int n = matrix.size();
        vector<vector<int>> dp(n, vector<int>(n));
        copy(matrix[0].begin(), matrix[0].end(), dp[0].begin());
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int mn = dp[i - 1][j];
                if (j > 0) {
                    mn = min(mn, dp[i - 1][j - 1]);
                }
                if (j < n - 1) {
                    mn = min(mn, dp[i - 1][j + 1]);
                }
                dp[i][j] = mn + matrix[i][j];
            }
        }
        return *min_element(dp[n - 1].begin(), dp[n - 1].end());
    }
//INT_MAX = 2 ^ 31 - 1，INT_MIN = -2 ^ 31.
//防止越界，在左边，上面和右边都增加一行
//并且将第一行定义为0
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>&amp; matrix) {

        int m = matrix.size(), n = matrix[0].size();

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

        for (auto&amp; e : dp[0]) e = 0; 

        for (int i = 1; i <= m; i++) {  
            for (int j = 1; j <= n; j++) {  
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1]))


                    + matrix[i - 1][j - 1];  
            }
        }
        int ans = INT_MAX;  

        for (const auto&amp; k : dp[m]) ans = min(ans, k);  
        return ans;  
    }
};

使用最小花费爬楼梯

题目

使用递归操作的几个步骤
1.明确dp[]函数的含义
2.明确关系式
3.进行初始化操作
4.确定遍历操作

class Solution {
    //本题是要求跳到最后一个台阶+1的位置
    public int minCostClimbingStairs(int[] cost) {  
        int len = cost.length;  
        //dp表示停留在第i个台阶上的花费  
        int[] dp = new int[len + 1];  
        //可以从第一个或第0个台阶起跳  
        dp[0] = 0;  
        dp[1] = 0;  
        //到达第i个台阶要么是从dp[i-2]跳两个台阶上来，要么从do[i-1]跳一个台阶上来  
        for (int i = 2; i <= len; i++) {  
            dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);


        }
        return dp[len];  
    }

整数拆分

题目

递归操作

1.确定dp数组含义
dp[i]：分拆数字i，可以得到的最大乘积为dp[i]
2.明确关系式
3.数组初始化
4.遍历顺序

大佬讲解
（无敌解释）

class Solution       {
public:
    /**
     * 1. 确定dp数组下标含义 分拆数字i，可以得到的最大乘积为dp[i];
     * 2. 递推公式 dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j);
     * 3. 初始化 dp[2] = 1;
     * 4. 遍历顺序 从前向后遍历就可以;
     * 5. 推导结果;
     */
    int integerBreak(int n) {
        /* 定义dp数组 */
        vector<int> dp(n + 1); 
        /* dp数组初始化 */  
        dp[2] = 1;  
        /* 从前向后遍历 */  
        for (int i = 3; i <= n ; i++) {  
            /* j遍历到小于i的值 */  
            for (int j = 1; j < i - 1; j++) {  
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));  
            }
        }
        return dp[n];  
    }
};

不同的二叉搜索树

问题分析：
使用动态规划的方法，
一：确定dp[i] 数组的含义，1到i节点组成的二叉搜索树的个数
二：寻找关系式，递推关系为 dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
三初始化， dp[0]=1,dp[1]=1
四：遍历

class Solution {
    /*
    dp[i] = i个不同的数组成的二叉搜索数的个数
    假设 i = 5
    当根节点等于 1 时 ，其余数字都比1大，只能在右边 dp[i] += dp[4]
    当根节点等于 2 时，左边有一个1比2小，右边有三个比2大的数字 dp[i] += dp[1] * dp[3]
    当根节点等于 3 时，左边有两个数比3小，右边有两个数比3大的数字 dp[i] += dp[2] * dp[2]
    ...
    知道根节点等于5，左边有4个数字比5小，只能放在5的左边,dp[i] += dp[4]
     */
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;//初始化0和1节点的情况
        for (int i = 2; i <= n; i++) {  
            for (int j = 1; j <= i; j++) {  
                int leftNum = dp[j - 1];  
                int rightNum = dp[i - j];  
                dp[i] += leftNum * rightNum;//对于第i个节点，需要考虑1作为根节点直到  
            }//i作为根节点的情况，所以需要累加  
            //一共有i个节点，对于根节点j时，左子树的节点个数为j-1，右子树的节点个数为i-j  
        }
        return dp[n];  
    }
}

最小路径和

别的就不多说，直接就是开涮

//需要注意点：为了简化代码，需要在上面和左边加上一行
//然后初始化的时候，需要将第一个位置上面的位置初始化为0
class Solution {
public:
    int minPathSum(vector<vector<int>>&amp; grid) {
        int m = grid.size(), n = grid[0].size(); 
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));

        dp[0][1] = 0; 

        //是从1的位置进行遍历  
        for (int i = 1; i <= m; i++) {    
            for (int j = 1; j <= n; j++) {    
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];




            }
        }
        return dp[m][n];    
    }
};

地下城游戏

直接就是感觉懵逼了。。。
但是遇到困难就需要想到 all is well
all is well
all is well
all is well
…

第一步：dp[i][j]的含义= dp[i][j] 表示从[i，j] 出发，到达终点需要的最低血量。
第二步：

1. 往右走一格直到终点：dp[i][j] + d[i][j] >= dp[i][j + 1]
   这个的意思是，dp[i][j] 到终点的最低健康点数要大于或等于右边一格
2. 往下走一格直到终点：dp[i][j] + d[i][j] >= dp[i + 1][j]
   这个的意思是，dp[i][j] 到终点的最低健康点数要大于或等于下面一格
   右边一格 dp[i][j + 1] 下面一格 dp[i + 1][j]
   要求的是最低健康点数，所以求出他们的最小值
   dp[i][j] = min(dp[i][j + 1]，dp[i + 1][j]) – d[i][j]

注意点，有可能出现个很大的血包，导致负血的状态出现，我们可以用：
dp[i][j] = max(1，dp[i][j]) 如果出现负血，就换成1血。
状态转换方程
// dp[i][j] = min(dp[i+1][j],dp[i][j+1]) – m[i][j];
// if(dp[i][j]<0)
// dp[i][j] = 1

• 初始化，为了防止越界，所以增加了一行和一列，并且在最左边或者最下面一个位置进行初始化

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>&amp; dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[m - 1][n] = 1;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];
                dp[i][j] = max(dp[i][j], 1);
            }
        }
        return dp[0][0];
    }
};

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        //状态表示 dp[i][j], 从该位置到终点所需的最小健康点数
        int m = dungeon.size();
        int n = dungeon[0].size();

        //dp表 初始化
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[m][n - 1] = 1;

        for (int i = m - 1; i >= 0; --i)
        {
            for (int j = n - 1; j >= 0; --j)
            {
                dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                if (dp[i][j] <= 0)
                    dp[i][j] = 1;
            }
        }

        return dp[0][0];

        //         状态转换方程
        //          dp[i][j] = min(dp[i+1][j],dp[i][j+1]) - m[i][j];
        //          if(dp[i][j]<0)
        //              dp[i][j] = 1;

    }
};

代码007普通

打赏 收藏 海报 链接