Binary Tree Paths
思路：
D&C，很直接
实现：
在整合path的时候用到paths.add(root.val + "->" + path), 当root为叶节点的时候要单独处理。paths.add(""+root.val).
D&C，很直接
实现：
在整合path的时候用到paths.add(root.val + "->" + path), 当root为叶节点的时候要单独处理。paths.add(""+root.val).
Backpack IV
思路： 马甲题 state: dp[i][j],体积为j时，前i个物品能够占满j体积所需要的方法数。 transition: dp[i][j]+=dp[i-1][j]+dp[i-1][j-k*nums[i-1]], k>=0 && k*nums[i-1]<=j 实现： dp[i][0]需要设置初始值为1，表示体积为0时，前i个物品能取的方法数为1，就是不取。 方法2 ： 用一维数组来做dp[j]=dp[j]+dp[j-nums[i-1]],右边的dp[j]表示前i-1个物品能够取体积为j的方法，因为暂时没有更新。实现的时候是nums[i-1]<=j<=tagert，j是从小到大，因为这道题允许物品重复。在j-nums[i-1]>nums[i-1]这种情况下，dp[j-num[i-1]]就会被更新也就是重复的情况。
评论
发表评论