动态规划 03

Author： Quan
发布时间：December 14, 2020
2864views
One comment
423 words
Categories：主页代码笔记

## 练习

#### 题目1：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 400

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber

题解：

```java
class Solution {
    public int rob(int[] nums) {
        // 最后一步 要么偷最后一家要么倒数第二家
        // 子问题
        // 偷最后一家：f[x-1]=max(f[x-2],f[x-3])
        // 偷倒数第二家：f[x-1]=max(f[x-3],f[x-4])

// 金额只与当前房屋和前一间有关

// // v1
        // int length = nums.length;
        // int[] f=new int[length];
        // int res=Integer.MIN_VALUE;
        // if(length<=0){
        //     return 0;
        // }else {
        //     if(length<=1){
        //         return nums[0];//长度为 1 时返回第一家
        //     }
        //     f[0]=nums[0];
        //     f[1]=Math.max(nums[0],nums[1]);// 两家时，二选一
        //     res = Math.max(f[0],f[1]);
        // }
        // if(length>2){
        //     f[2]=nums[0]+nums[2];
        //     res = Math.max(f[2],res);// 三家时
        // }
        // for(int i=3;i<length;i++){
        //     f[i] = Math.max(f[i-2],f[i-3]);//偷前面第2家 和 前面第3家
        //     f[i] += nums[i];
        //     res = Math.max(f[i],res);
        // }
        // return res;

// v2 空间优化
        if(nums==null||nums.length<=0){
            return 0;
        }
        int length = nums.length;
        if(length==1){
            return nums[0];
        }
        int first = nums[0];
        int second = Math.max(first,nums[1]);
        for(int i=2;i<length;i++){
            int tmp = second;
            second = Math.max(first+nums[i],second);
            first = tmp;
        }
        return second;
    }
}
```

#### 题目2：

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

输入: 2
输出: [0,1,1]
示例 2:

输入: 5
输出: [0,1,1,2,1,2]
进阶:

给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
要求算法的空间复杂度为O(n)。
你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/counting-bits

题解：

![image-20201214142714950](https://cdn.jsdelivr.net/gh/Quan666/CDN/pic/image-20201214142714950.png)

```java
public class Solution {
  public int[] countBits(int num) {
      int[] ans = new int[num + 1];
      for (int i = 1; i <= num; ++i)
        ans[i] = ans[i >> 1] + (i & 1); // x / 2 is x >> 1 and x % 2 is x & 1
      return ans;
  }
}
```

#### 题目3：

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

![img](https://cdn.jsdelivr.net/gh/Quan666/CDN/pic/minpath.jpg)

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum

题解：

```java
class Solution {
    public int minPathSum(int[][] grid) {
        // 最后一步
        // f[m][n] = max(f[m-1][n],f[m][n-1])
        // 边界 m=0 or n=0 ,f[0][0]=grid[0][0]

// int x_length=grid.length;
        // int y_length=grid[0].length;
        
        // int[][] f = new int[x_length][y_length];

// f[0][0]=grid[0][0];
        // for(int x=0;x<x_length;x++){
        //     for(int y=0;y<y_length;y++){
        //         if(x==0&&y==0){
        //             continue;
        //         }
        //         if(x==0){
        //             f[x][y]=f[x][y-1]+grid[x][y];
        //         }else if(y==0){
        //             f[x][y]=f[x-1][y]+grid[x][y];
        //         }else{
        //             f[x][y]=Math.min(f[x-1][y],f[x][y-1])+grid[x][y];
        //         }
        //     }
        // }
        // return f[x_length-1][y_length-1];

// v2 空间优化
        int x_length=grid.length;
        int y_length=grid[0].length;
        
        // int[][] f = new int[x_length][y_length];

// f[0][0]=grid[0][0];
        for(int x=0;x<x_length;x++){
            for(int y=0;y<y_length;y++){
                if(x==0&&y==0){
                    continue;
                }
                if(x==0){
                    grid[x][y]=grid[x][y-1]+grid[x][y];
                }else if(y==0){
                    grid[x][y]=grid[x-1][y]+grid[x][y];
                }else{
                    grid[x][y]=Math.min(grid[x-1][y],grid[x][y-1])+grid[x][y];
                }
            }
        }
        return grid[x_length-1][y_length-1];
    }
}
```

Last modification：December 14th, 2020 at 04:57 pm

If you think my article is useful to you, please feel free to appreciate

One comment

smallstars
December 14th, 2020 at 04:57 pm

tql,sdl,ddw,wsl

Reply

动态规划 03

Quan • 2020 年 12 月 14 日

## 练习

#### 题目1：

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 400

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber

题解：

// 金额只与当前房屋和前一间有关

#### 题目2：

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

输入: 2
输出: [0,1,1]
示例 2:

输入: 5
输出: [0,1,1,2,1,2]
进阶:

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/counting-bits

题解：

![image-20201214142714950](https://cdn.jsdelivr.net/gh/Quan666/CDN/pic/image-20201214142714950.png)

#### 题目3：

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

![img](https://cdn.jsdelivr.net/gh/Quan666/CDN/pic/minpath.jpg)

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum

题解：

```java
class Solution {
    public int minPathSum(int[][] grid) {
        // 最后一步
        // f[m][n] = max(f[m-1][n],f[m][n-1])
        // 边界 m=0 or n=0 ,f[0][0]=grid[0][0]

// int x_length=grid.length;
        // int y_length=grid[0].length;
        
        // int[][] f = new int[x_length][y_length];

// v2 空间优化
        int x_length=grid.length;
        int y_length=grid[0].length;
        
        // int[][] f = new int[x_length][y_length];

动态规划 03

Leave a Comment Cancel reply

One comment

自建 RSSHub 公开使用说明

ELF_RSS 订阅插件使用、安装教程

天翼云盘目录直链解析批量下载

酷Q 推特转发机器人插件

酷Q RSS订阅转发插件安装教程实现Twitter、YouTube等转发

QRCode.js：使用 JavaScript 生成二维码以及解决无法生成带中文字符url问题

qbittorrent 实现自动下载番剧更新并在线播放

百度贴吧帖子备份爬虫

二叉树先序、中序、后续遍历

动态规划 01

动态规划 03