程序猿大队长

题解

/ 注册

全部文章 / 题解（共4篇）

题解 | #不相邻取数#

思路本题是个动态规划问题，所以按照动态规划的解题步骤来思考问题 1.确定状态本题无非就是要找到一些不相邻数的数，使得它们的和最大。状态可以很自然的想到可以用元素和来表示。 2.确定dp数组含义 dp[i]表示以arr[i]为结尾元素时的最大值 3.确定选择针对第i个元素arr[i]，要从dp[...

Java

2021-12-04

5 668

题解 | #连续子数组最大和(ACM版本)#

解题步骤 1.确定状态数组下标不断移动，在移动过程中，最大子数组也不断变化，所以状态为子数组最大值。 2.确定dp数组在本题中，可定义一维数组dp[x]，其中dp[i]表示以第i个元素结尾最大子数组的值 3.确定选择针对第i个元素，实际上是有两种选择，一种是与arr[i-1]相连，形成一个最大...

Java

2021-12-02

5 748

题解 | #0-1背包和完全背包#

一、0-1背包第一类问题：最大价值确定状态容量+剩余物品数量确定选择针对一个物品放入背包或者不放入背包两种选择确定dp含义 dp[i][j]表示针对前i个物品，在容量为j的限制下，所能存放的最大价值确定base case 当物品数量为0或者背包体积为0时，最大价值为0，即dp[0][...

Java 动态规划

2021-11-30

22 1193

题解 | #连续子数组的最大和#

重点是要想到新建一个数组，用来存放以原数组中每个数结尾的最大连续子数组的最大和。假设当前遍历到index=n,则当以arr[index]为尾的最大连续子数组和等于max(以arr[index-1]为尾的最大连续子数组的和,arr[index]);

Java

2021-11-19

0 318