算法:动态规划 动态规划

动态规划是研究一类最优化问题的方法,在经济、工程技术、企业管理、工农业生产及军事等领域中都有广泛的应用。近年来,在ACM/ICPC中,使用动态规划(或部分应用动态规划思维)求解的题不仅常见,而且形式也多种多样。而在与此相近的各类信息学竞赛中,应用动态规划解题已经成为一种趋势,这和动态规划的优势不无关系。 1、动态规划的常用名词 在学习动态规划之前,先得对下面的名词有所了解。本书将标准名词作了一些简化,便于大家更好的理解。 (1)状态(smte) 对于一个问题,所有可能到达的情况(包括初始情况和目标情况)都称为这个问题的一个状态。 (2)状态变量(sk)