蒟蒻不会DP，找了20道入门题来刷，分享下转移过程，发现做dp最笨的方式就是画状态矩阵找转移方程，然后一些基本的经典DP要记住，剩下就是他们的变形了，背包又忘得差不多了，感觉下次得找个时间补一下。。。POJ1050非常经典，用捆绑法将二维问题转化到一维的状态来求解。
【水|POJ动态规划20题，一句话题解~】poj 1050 √最大子矩阵和：捆绑子矩阵转化为最大连续子段和问题
poj 1088 √四方向记忆化搜索dp[i][j]=max(dp[i-1][j]...)+1遍历所
有点，注意处理边界
poj 1163 √数塔dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]
poj 1159 √dp[s][e]=min(dp[s+1][e],dp[s][e-1])+1 字符不同
poj 3280 √dp[i][j]=min(dp[i+1][j]+cost[s[i]-'a'],
dp[i][j-1]+cost[s[j]-'a'])
poj 3616 √dp[i]=max(dp[i],dp[j]+a[i].w) a[i].s>=a[j].e+r
poj 1458 √lcs dp[i][j]=max(dp[i-1][j],dp[i][j-1])||dp[i-1]
[j-1]+1
poj 1579 √记忆化搜索
poj 2081 √(dp[i-1]-i>=0)? dp[i]=dp[i-1]-i :dp[i]=dp[i-1]+i
poj 1953 √FIB
poj 2250 √LCS用string处理
poj 1887 √LDS
poj 2533 √LIS
poj 1631 √LIS nlogn
poj 1080 √LCS变形 预处理边界和加'-'后的配对情况
poj 2192 √c[i+j]==b[j]&&dp[i][j-1]==1||c[i+j]==a[i]&&dp[i-1][j]==1dp[i][j]=1画转移矩阵
poj 3356 √LCS变形 dp[i][j]=min(a[i-1]==b[j-1]?dp[i-1][j-1],dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1)
poj 1157 √dp[i][j]=max(dp[i-1][j-1]+a[i][j],dp[i][j-1])
poj 1014 √多重背包化01背包
poj 1125 √多源最短路中最大值的最小者FLOYD暴过
推荐阅读
- 题目|C. Ayoub and Lost Array（思维dp）
- HDU 5185 Equation (DP)
- dp|AC Challenge(状态压缩DP)
- 题解|【HNOI2017】大佬-dalao
- CodeForces - 1282B2 B2. K for the Price of One (Hard Version)
- 经典题|3462: DZY Loves Math II
- Android|【常用工具类】DensityUtils（dp px 互相转换）