google网站,app网站开发住房公积金,自己制作一个网站的软件,网站优化外包服务打家劫舍和背包问题一样是一道非常经典的动态规划问题#xff0c;只要做过几道动态规划的题#xff0c;这道题简直就非常容易做出来。我应该花了10来分钟左右就写出来了#xff0c;动态规划问题最重要的就是建立状态转移方程#xff0c;就是说如何从上一个状态转移到下一个… 打家劫舍和背包问题一样是一道非常经典的动态规划问题只要做过几道动态规划的题这道题简直就非常容易做出来。我应该花了10来分钟左右就写出来了动态规划问题最重要的就是建立状态转移方程就是说如何从上一个状态转移到下一个状态的。直观的说就是dp[i]是怎么来的是通过dp[i-1]来的还是通过dp[i-2]来的等等如果知道初始状态和状态转移方程那么每个状态都可以算出来以下是我的代码
class Solution {public int rob(int[] nums) {int n nums.length;int[][] dp new int[n][2];dp[0][0] 0;dp[0][1] nums[0];int max Math.max(dp[0][0], dp[0][1]);for(int i1;in;i){dp[i][0] max;dp[i][1] dp[i-1][0]nums[i];max Math.max(dp[i][0], dp[i][1]);}return max;}
} 数组大小是n我建立一个int[n][2]的dp数组其中dp[i][0]表示不偷第i家能获得的最大的价值dp[i][1]表示偷第i家能获得的最大的价值。max表是dp[i][0]和dp[i][1]中的最大值表示偷到第i家能获得的最大价值(因为是从第0家偷到第n-1家的)。
初始状态dp[0][0]0; 表示不偷第0家dp[0][1]nums[0];表示偷第0家。
状态转移方程dp[i][0] max;这个max是dp[i-1]的最大值就是说如果我不偷第i家那么第i-1家偷不偷都可以所以不偷第i家的最大值就是第i-1家的最大值与偷不偷i-1无关。
dp[i][1] dp[i-1][0]nums[i];偷第i家的最大值就是不偷第i-1家的最大值dp[i-1][0]第i家的价值nums[i];
最后只要返回dp[n-1][0]和dp[n-1][1]中的最大值即可而max正好是两者中的最大值所以只要返回max即可。
动态规划问题都是这个套路找到状态转移方程通过初始状态算出每个状态返回最后那个状态或者返回所有状态中的最值。
看看题解有没有新颖的解法。
题解的思路确实更清晰他dp数组是一维的没有分什么偷和不偷dp[i]就表示在第i家的最大价值也就是max那么状态转移方程就是dp[i] Math.max(dp[i - 2] nums[i], dp[i - 1]);dp[i-2]nums[i]表示偷第i家那么就是在第i-2家的最大值家上nums[i]dp[i-1]就是不偷第i家那么就是第i-1家的最大值。dp[i]取两者中的最大值即可。
class Solution {public int rob(int[] nums) {if (nums null || nums.length 0) {return 0;}int length nums.length;if (length 1) {return nums[0];}int[] dp new int[length];dp[0] nums[0];dp[1] Math.max(nums[0], nums[1]);for (int i 2; i length; i) {dp[i] Math.max(dp[i - 2] nums[i], dp[i - 1]);}return dp[length - 1];}
}
