动态规划随笔

DP写程序的循环怎么开始:
看初始状态是是什么,再看状态转移方程是什么依赖顺序
比如LC375 初始状态 dp[i][i] = 0 转移方程dp[i][j] = min (i<=k<=j) { k + max(dp[i][k-1], dp[k+1][j]) }
那么明显是由初始状态看是从某一点向外扩展,由转移方程看是从低到高,所以循环为:
for (int i = 1; l < n; l++)
for (int i= 1;i <= n-l; i++) {
int j = i+l;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k <= j; k++)
dp[i][j] = Math.min(dp[i][j], k + Math.max(dp[i][k - 1], dp[k + 1][j]));
}
return dp[1][n];
}

先(1,2)(2,3)。。。。(n,n+1) 再(1,3)(2,4)。。。。这样拓展

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长...
    廖少少阅读 3,343评论 0 18
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,779评论 0 33
  • 回溯算法 回溯法:也称为试探法,它并不考虑问题规模的大小,而是从问题的最明显的最小规模开始逐步求解出可能的答案,并...
    fredal阅读 13,763评论 0 89
  • 树形动态规划,顾名思义就是树+DP,先分别回顾一下基本内容吧:动态规划:问题可以分解成若干相互联系的阶段,在每一个...
    Mr_chong阅读 1,522评论 0 2
  • 1. 分层的优势 利用这样分层的体系结构,开发者可以讨论一个定义良好的、大而复杂的系统的特定部分。这种简化本身由于...
    温柔虎阅读 546评论 0 1