往googler的路上day4
今日收穫:
動態規劃解題步驟
1.確定狀態
(1)一般來說動態規劃都需要開一個數組 ex:f[i], f[i][j]
(2)最後一步
(3)子問題
(4)透過將計算結果保存下來，並改變計算順序
2.轉移方程
(1)列出方程式
(2)想想子問題即最終問題大概能夠怎麼用數學來列出來
3.初始條件和邊界情況
ex: f(0) = 0 不能越界 問f(0–1)=?
4.計算順序
大部分題目:
(1)一維:從小到大從左到右
二維:從左到右從上到下
//順序原因是因為會用到以前的結果
(2)當我們計算f(x)時，f(x-2), f(x-5), f(x-7)都算過了 //換零錢問題
5.通常都會建陣列，利用前面建好的陣列得到後面的結果，再藉由問題
分析(一些if else)得到完整方程式//重要的廢話
解題路程
一、換零錢
//https://www.lintcode.com/problem/669/
1.避開負數問題
2.從左邊到右邊，要先製造已存結果
Code
二、Longest Common Subset
1.藉由建造表格來解題 //非常令人印象深刻的使用子問題解法
2.兩陣列 s1[]={a,b,c,d}, s2[] = {a,c,d,e}
當第一個陣列c到第二個陣列b中解找出最佳解，用
(1)目前指向兩元素是否相等，若不相等，則從目前指向方式的前一步
(兩元素兩種前一步)來決定。
Code
三、走迷宮 //https://www.lintcode.com/problem/114/
1.完全跟高中數學走迷宮一樣，幾種方法真的用加的
//資料來源:https://reurl.cc/5o8RKz 1:05:03
Code
四、最大子陣列 //https://cses.fi/problemset/task/1643
1.小問題是目前從左到右相加最大值是多少，每次都比較，則必定得到解。
2. if(sum < 0) sum = 0;是一個impressive的作法，相當精彩
Code
五、跳青蛙 // 今天回想時不夠清楚，日後需複習
//https://www.lintcode.com/problem/116/
1.再問這個問題時，要問最後一顆石頭能否跳可以問最後一顆石頭的上一顆石頭能不能踩，以及距離是否足夠跳過來。
2.確認好這顆石頭可以立足
3.確認好從這顆石頭跳下去可以超越到達最外層for迴圈所指向的石頭
Code
六、Longest Increasing Subsequence //這題因為是下學期作業，不放code
1.發現再做了上面五題之後，這題在不看解答的情況下，自己歸納出了子題已即列出方程
2.最後一試再試如同MIT教授所說的把每種可能試一遍後，得出了結果。
今日心得:
今天算是有盡力的一天吧，發現運動也是蠻佔精力的，但是要堅持啊!
解了這些題目覺得離目標又更進一步了!開學後勢必會更不容易，加油!
