当前位置：首页 > article >正文

力扣动态规划-5【算法学习day.99】

article 2025/1/24 22:04:08

前言

###我做这类文章一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？建议灵神的题单和代码随想录）和记录自己的学习过程，我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.打家劫舍II

题目链接:213. 打家劫舍 II - 力扣（LeetCode）

题面:

分析:这题主要难点在于最后一个和第一个的考虑上，我这边解决麻烦了点但更好理解，用两个数组，分别表示第一个选了和第一个没选

代码:

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n==1)return nums[0];
        int[][] flag = new int[n][2];
        int[][] flag2 = new int[n][2];
        flag[0][0] = 0;
        flag[0][1] = nums[0];
        flag2[0][0] = 0;
        flag2[0][1] = 0;
        for(int i = 1;i<n;i++){
            flag[i][0] = Math.max(flag[i-1][1],flag[i-1][0]);
            flag[i][1] = flag[i-1][0]+nums[i];
            flag2[i][0] = Math.max(flag2[i-1][1],flag2[i-1][0]);
            flag2[i][1] = flag2[i-1][0]+nums[i];
        }
        return Math.max(flag[n-1][0],Math.max(flag2[n-1][0],flag2[n-1][1]));
    }
}