货币系统一(DP[i][j]二维) 2024-05-18 算法, 动态规划, 数据结构 68人 已看 奶牛手上有N枚硬币，第i枚硬币的面值是d[i]元。无人售货机有1000件礼物，编号从1至1000，第i件礼物需要i元，售货机不设找赎。第一行，一个整数N，1<=N<=40。第二行，N个整数，第i个整数是d[i]，1<=d[i]<=100。dp[i][j]=1 (j>=a[i] &&dp[i-1][j-a[i]==1） //用第i个硬币。2．状态：dp[i][j]表示用第i个硬币组合时，能否表示面值j；dp[i][j]=dp[i-1][j] //不用第i个硬币。一行，从小到大输出不可能买得到的礼物的编号。
代码随想录算法训练营第四十七天|198.打家劫舍 213.打家劫舍II 337.打家劫舍III 2024-05-22 算法, leetcode, 动态规划, 职场和发展 76人 已看 如果不偷当前节点：取左右孩子偷或不偷的最大值，int val2=max(left[0],left[1])+max(right[0],right[1]);如果偷当前节点：左右孩子不偷，int val1=cur->val+left[0]+right[0]但是递推公式dp[i]=max(dp[i-2]+nums[i],dp[i-1]);如果数组只有一个元素，dp[i]=nums[0];偷i：dp[i]=dp[i-2]+nums[i]dp[i]:i以内的房屋，偷的金额最大值。不偷i：dp[i]=dp[i-1];
动态规划--钢条切割问题 2024-05-14 算法, 动态规划, 代理模式 92人 已看 动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。动态规划和分治法相似，都是通过组合子问题的解来求解原问题。分治法讲问题划分成互不相交的子问题，递归求解子问题，再将他们的解组合起来，求出原问题的解。与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。在这种情况下，分治算法会做出许多不必要的工作，它会反复的求解那些公共子问题。而动态规划算法对每个子子问题只求解一次，将结果保存到表格中，从而无需每次求解一个子子问题都要重新计算。
C++ 509. 斐波那契数 2024-05-09 算法, c++, leetcode, 动态规划, 开发语言 70人 已看 解释：F(2) = F(1) + F(0) = 1 + 0 = 1。解释：F(3) = F(2) + F(1) = 1 + 1 = 2。解释：F(4) = F(3) + F(2) = 2 + 1 = 3。
代码随想录算法训练营第四十七天 2024-05-09 算法, 图论, 动态规划 98人 已看 这题我想的有点过于简单，导致看起来很乱，所以还是要先把打家劫舍1的搭建好，然后找起始结束，这样不乱，max(val1,val2)这种。我感觉我这个比随想录那个更清晰呢。今天上班只完成了一道题，被同事发现了，gg，果断溜回来做剩下的两道，加油吧xd，离新的工作越来越近了。打家劫舍1没有太多好说的，就是能搞定[i-2]和[i-1]取最大即可。通过vectordp(2,0)，分成用当前结点和不用当前节点。213.打家劫舍II。337.打家劫舍III。不用当前节点的情况，
leetcode63.跳跃游戏2（动态规划） 2024-05-09 算法, leetcode, 游戏, 动态规划, 职场和发展 109人 已看 断对应的节点是不是有障碍，如果有，直接返回0，没有就必须知道到达dp[i - 1][j]有多少条路径，还有到达dp[i][j - 1]有多少条路径，这两条路径不是二选一，而是全都满足条件，所以应该全部加到。dp[m][n],应为添加了虚拟节点，数组也变大了，所以要求的结果是对应dp[m][n]，其中m是行数。其实在添加了一行一列辅助虚拟节点之后，最需要虚拟节点的是原来的第一行和第一列的dp数组表。那么元dp数组的左上角应该填的是什么，从起点出发到达起点只有一种方法，所以应该填写1，但。
C++ 62. 不同路径 2024-05-09 算法, c++, leetcode, 动态规划, 开发语言 88人 已看 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。问总共有多少条不同的路径？
力扣：931. 下降路径最小和 2024-05-06 算法, leetcode, 动态规划, 职场和发展, 数据结构 79人 已看 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。如图所示，为和最小的两条下降路径。如图所示，为和最小的下降路径。，请你找出并返回通过。
LeetCode热题100｜动态规划Part.1｜70.爬楼梯、118.杨辉三角、198.打家劫舍 2024-05-07 算法, leetcode, 动态规划, 职场和发展 101人 已看 也就是每个数字等于上一行左右两个数字之和，但是需要注意的是， 每一行的最左边和最右边的数字必须是1.最直接的方式就是直接全部初始化成1，因为每一行除了第一个和最后一个元素，我们都能通过递推公式进行推导。这里需要注意的是，由于每一行的元素个数都是变化的，所以关于行的初始化一定要在外循环中处理。基本思路就是先构造一个result存储最终的结果，然后定义一个dp数组来计算每一行的结果。在leetcode的题目展示上面已经看的很清楚了，杨辉三角中每个数字等于上一行的左右两个数字之和。还是比较简单的，这里就不写了。
代码随想录学习Day 34 2024-05-07 学习, 算法, leetcode, 动态规划, 职场和发展 120人 已看 5.举例推导dp数组：m = 3，n = 7时，dp = [[1, 1, 1, 1, 1, 1, 1], [1, 2, 3, 4, 5, 6, 7], [1, 3, 6, 10, 15, 21, 28]]4.确定遍历顺序：因为递推公式为dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。1.确定dp数组及其下标的含义：dp[i][j]的含义是从(0, 0)走到(i, j)所需的步数；
