hot100之动态规划上
<h3 id="爬楼梯070">爬楼梯(070)</h3><pre><code class="language-java">class Solution {
int[] memo = new int;
public int climbStairs(int n) {
if (memo != 0) return memo;
if (n == 0|| n ==1 ){
return 1;
}
if (n == 2){
return 2;
}
memo = climbStairs(n-1) + climbStairs(n-2);
return memo;
}
}
</code></pre>
<ul>
<li>废话</li>
</ul>
<p><s>这题真是从小做到大</s></p>
<p>感觉动态规划就好像 递归的记忆化</p>
<h3 id="杨辉三角118">杨辉三角(118)</h3>
<pre><code class="language-java">class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<>();
res.add(new ArrayList<>(Arrays.asList(1)));
for (int i = 1; i < numRows; i++){
List<Integer> layer = new ArrayList<>();
layer.add(1);
for (int j = 1; j < i; j++){
layer.add(res.get(i-1).get(j-1) + res.get(i-1).get(j));
}
layer.add(1);
res.add(layer);
}
return res;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>可以看作给每层作dp</p>
<h3 id="打家劫舍198">打家劫舍(198)</h3>
<pre><code class="language-java">class Solution {
public int rob(int[] nums) {
int n = nums.length;
int[] dp = new int[];
for (int i = 0; i < n; i++){
dp = Math.max(dp+nums, dp);
}
return dp;
}
}
</code></pre>
<p>优化空间</p>
<pre><code class="language-java">class Solution {
public int rob(int[] nums){
int dp_0 = 0;
int dp = 0;
for (int num : nums){
int dp_new = Math.max(dp, dp_0 + num);
dp_0 = dp;
dp = dp_new;
}
return dp;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>dp与dp作为基础态</p>
<p>因为dp要由dp和dp共同决定 dp与dp前置条件不足</p>
<p><strong>优化空间</strong></p>
<p>因为dp只由dp和dp决定, 返回结果也只需要最终值</p>
<p>通过<code>dp_0</code><code>dp</code> 保存所需前状态</p>
<ul>
<li>感悟</li>
</ul>
<p>dp保存区间能赚到的最大值</p>
<h3 id="完全平方数279">完全平方数(279)</h3>
<pre><code class="language-java">class Solution {
public int numSquares(int n) {
int[] dp = new int;
dp = 0;
for (int i = 1; i <= n; i++){
int min = Integer.MAX_VALUE;
for (int j =1; j*j <= i; j++){
min = Math.min(min, dp);
}
dp = min + 1;
}
return dp;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>两层循环, 内部循环作 <code>i - j * j</code> 遍历 j的平方</p>
<h3 id="零钱兑换322">零钱兑换(322)</h3>
<pre><code class="language-java">class Solution {
public int coinChange(int[] coins, int amount) {
Arrays.sort(coins);
int[] dp = new int;
dp = 0;
for (int i = 1; i <= amount; i++){
int min = 10000;
for (int coin : coins){
if (i < coin){
dp = min;
continue;
}
min = Math.min(min, dp);
}
dp = min+1;
}
return dp > 10000 ? -1 : dp;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>先对coins作sort, 修剪枝叶, 再二层循环</p>
<h3 id="单词拆分139">单词拆分(139)</h3>
<pre><code class="language-java">class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean;
dp = true;
for (int i = 1; i <= s.length(); i++){
for (String word : wordDict){
if (i >= word.length() && dp && word.equals(s.substring(i- word.length(), i))){
dp = true;
break;
}
}
}
return dp;
}
}
</code></pre><br><br>
来源：https://www.cnblogs.com/many-bucket/p/18944163
頁:
[1]