关键词：
【中文标题】DP数组初始化的原因【英文标题】：Reason for such initialization of DP array 【发布时间】：2017-10-08 21:11:47 【问题描述】：我正在解决来自 LeetCode.com 的a question。问题是这样的：
你是一名职业强盗，计划抢劫沿街的房屋。每栋房子都藏有一定数量的金钱，唯一阻止你抢劫的限制是相邻的房子都连接了安全系统，如果同一晚两栋相邻的房子被闯入，它会自动联系警察。 给定一个代表每所房子的金额的非负整数列表，确定今晚你可以在不报警的情况下抢劫的最大金额。
想了一会儿，我可以得出以下关系，这是正确的：
dp[i] = max(dp[i-2]+nums[i], dp[i-1]);
但是，我无法初始化 dp[] 数组。在解决方案中，它已像这样初始化：
dp[0]=nums[0];
dp[1]=max(nums[0],nums[1]);
这不是错误的吗？因为如果nums[0]>nums[1]，那么它不就意味着抢劫同一所房子（因为我们将dp[0]和dp[1]都初始化为相同的值？）即使我们假设nums[1]>nums[0]，也不会nums[0]和nums[1]是连续的房子吗？
完整代码（如果需要）如下：
class Solution
public:
int rob(vector<int>& nums)
if(nums.empty())
return 0;
vector<int> dp(nums.size());
dp[0]=nums[0];
dp[1]=max(nums[0], nums[1]);
for(int i=2; i<nums.size(); i++)
dp[i] = max(nums[i]+dp[i-2], dp[i-1]);
return dp[nums.size()-1];
;
【问题讨论】：
大多数社区成员都在享受他们的秋季假期，或者我的问题的可见性受到限制。我不确定哪一个是真的。我多么怀念人们过去突袭回答（或投票）问题的时候！ 将dp[i] 视为“您可以在不报警的情况下从i+1 房屋中抢劫的最大金额”，并将每个i 视为一个单独的案例。如果有 1 所房子 (i == 0) 那么你只能从那一所房子里偷东西。如果有两间房子 (i == 1)，那么你最多可以偷到两间房子的最大值 (nums[0] or nums[1])。我的做法是int dp[i+1]; dp[0] = 0; dp[1] = nums[1]; ... return dp[nums.size()]，我认为这更直观。
@0x499602D2，是的，你的确实比我的更有意义！谢谢！
【参考方案1】：
在给出的解决方案中，将dp[i] 视为“您可以在不报警的情况下从i+1 房屋中抢劫的最大金额”，并将每个i 视为一个单独的案例。如果有 1 所房子 (i == 0) 那么你只能从那一所房子里偷东西。如果有两所房子（i == 1），那么您最多可以偷取任一房子的最大值（nums[0] 或 nums[1]）。我的做法是：
int n = nums.size();
int dp[n+1]; // max $ you can rob from i houses with altering police
dp[0] = 0; // no houses, no money
dp[1] = nums[0];
for (int i = 2; i <= n; ++i)
dp[i] = max(dp[i - 1], nums[i - 1] + dp[i - 2]);
return dp[n];
它返回你可以从i 房屋（不是i+1）窃取的最大金额，我认为这更容易理解。
【讨论】：
【参考方案2】：如果我理解正确，您的问题可以简化为：Because if nums[0]>nums[1], then doesn't it imply robbing the same house (because we initialize both dp[0] and dp[1] to the same value?)。
答案是否定的，这并不意味着抢劫同一所房子。这意味着不要抢劫房子 1，因为房子 0 被抢劫了。而房子 0 被抢劫了，因为它包含更多的钱，你必须在抢劫房子 0 或房子 1（钱少）之间做出选择。
【讨论】：
codeforces677dvanyaandtreasure
...值即可。每次扩展一层需要一个新的树状数组，因为每次初始化树状数组会超时，所以可以额外开一个数组记录一下每一个点是第几次更新的。#pragmacomment(linker,"/STA 查看详情
无法从成员变量中的初始化字符串中推断出数组大小的原因是啥？
】无法从成员变量中的初始化字符串中推断出数组大小的原因是啥？【英文标题】：Whatisthereasonfornotbeingabletodeducearraysizefrominitializer-stringinmembervariable?无法从成员变量中的初始化字符串中推断出数组大小的原因是什么？【发布时... 查看详情
[hdoj5542]thebattleofchibi（dp，树状数组）
...总数。更新就比较容易了，dp(i,j)=∑(k=1->j-1)dp(i-1,k)，初始化dp(i,1)=1。1#include<bits/ 查看详情
718.最长重复子数组(代码片段)
...值dp[0][0]classSolutionpublicintfindLength(int[]nums1,int[]nums2)//数组初始化大小需要注意多 查看详情
❤️思维导图整理大厂面试高频数组19:股票问题iii的dp数组构建/初始化和空间优化难点,力扣123❤️(代码片段)
此专栏文章是对力扣上算法题目各种方法的总结和归纳,整理出最重要的思路和知识重点并以思维导图形式呈现,当然也会加上我对导图的详解.目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解),毕竟算法不是做... 查看详情
❤️思维导图整理大厂面试高频数组19:股票问题iii的dp数组构建/初始化和空间优化难点,力扣123❤️(代码片段)
此专栏文章是对力扣上算法题目各种方法的总结和归纳,整理出最重要的思路和知识重点并以思维导图形式呈现,当然也会加上我对导图的详解.目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解),毕竟算法不是做... 查看详情
每日一练----1.21oj总结(代码片段)
...]的含义。递推公式。状态转移方程。遍历顺序。dp数组的初始化。定义dp数组，初始化数组中的每个值为最小值，dp[i]代表输入数组v的前i项和vector<int>dp(n,-1e5);状态转移为dp[i]与v[i]的关系dp[i]=dp[i-1]+v[i]>v[i]?dp[i-... 查看详情
代码随想录算法训练营第三十八天|509.斐波那契数70.爬楼梯746.使用最小花费爬楼梯(代码片段)
...#xff08;dptable）以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组509.斐波那契数视频讲解主要思路：1.确定dp数组以及下标的含义dp[i]的定义为：第i个数的斐波那契数值是dp[i]2.确定递推公式dp[i]&... 查看详情
更改用 inf 初始化的二维矩阵中的数组
】更改用inf初始化的二维矩阵中的数组【英文标题】：changeanarrayina2dmatrixinitializedwithinf【发布时间】：2022-01-1209:32:53【问题描述】：版本：python3代码很简单dp=[[float(\'inf\')]*3]*3dp[0][0]=1我得到了什么[[1,inf,inf],[1,inf,inf],[1,inf,inf]]我... 查看详情
动态规划学习笔记(代码片段)
...下标的含义（2）确定递推公式（3）dp数组初始化（4）确定遍历顺序（5）举例推导dp数组2.一维dp数组做题记录做题由简到难记录入门/简单题爬楼梯（1）确定dp[i]含义i表示阶梯层数dp[i]表示到... 查看详情
poj1185（状态压缩dp）
...组中多了一维保存上上一行。递推公式也变成求最大值。初始化的时候从dp[1][0][i]开始，0是根据st数组的起始。#include<algorithm>#include<cstdio>#include<cstring>#include<iostream>#defineMax1000 查看详情
状压dp终极篇（状态转移的思想）
...体操作为首先把状态压缩为二进制串，然后对第一行进行初始化，再利用三个for循环进行状态转移（第一层for循环控制行的前进，第二个和第三个for循环控制本行和上一行的状态）利用状态转移对二维数组进行不断的更新（可以... 查看详情
p2022有趣的数(二分&数位dp)(代码片段)
...dpdpdp数组开到lim,leadlim,leadlim,lead则每次checkcheckcheck都需要初始化dpdpd 查看详情
动态规划学习笔记(代码片段)
...下标的含义（2）确定递推公式（3）dp数组初始化（4）确定遍历顺序（5）举例推导dp数组2.一维 查看详情
在java开发中遇到stringindexoutofrange:4这是啥原因
...的解释是"程序遇上了空指针"，简单地说就是调用了未经初始化的对象或者是不存在的对象，这个错误经常出现在创建图片，调用数组这些操作中，比如图片未经初始化，或者图片创建时的路径错误等等。对数组操作中出现空指... 查看详情
动态规划学习笔记(代码片段)
...下标的含义（2）确定递推公式（3）dp数组初始化（4）确定遍历顺序（5& 查看详情
01背包完全背包(代码片段)
...复杂度O(nW)，空间复杂度O(nW)记得以下所有方法首先都要初始化dp数组memset(dp,0,sizeof(dp));dp[i][j]：表示从前i个物品中选出总重量不超过j的物品时总价值的最大值。intdp[MAX_N+1][MAX_W+1];voidsolve()for(inti=1;i<=n;i++)for(intj=0;j<=W;j++)if(j<... 查看详情
c.twoarrays(思维dp或组合数学)(代码片段)
...(q>=j))for(inti=1;i<=n;i++) for(intj=i;j<=n;j++) dp[1][i][j]=1;//初始化长度为1的时候 for(inti=2;i<=m;i++) for(intj=1;j<=n;j++) for(intq=j;q<=n;q++) for(intw=1;w<=j;w++)//升序 for(inte=q;e<=n;e++)//降序 dp[i][j][q]=(dp[i-1][w][e]+dp[i][j][q])%mod;(然而复杂... 查看详情