满足动态规划的条件
1.状态可以转移
2.满足动态方程
3.目标可解
经典题目三角形的最小路径和，
[r,c ]为当前的列数，r为当前所处高度|行所处行
valueof(r,c) 为当前路径的值(最小值)
转移条件为当前行的最小值,转移次数是
[[0, 0]2,4,6,8,10....,2*(r-1)]
当r=0 min(r,0)=valueof(r,0)+valueof(r-1,0)
当c=r-1 min(r,c)=valueof(r,c)+valueof(r-1,c-1)
orther valueof(r,c)=min(valueof(r-1,c-1),valueof(r-1,c))+valueof(r,c)
程序实现的空间复杂度O(1)
时间复杂度为转移总次数
[0,0,4,6,...2*r-2]
题目 题解 数字=左边数乘积*右边数乘积
动态规划26 一、LC 509 斐波那契数列问题 基本盘解法(自顶向下) 6-->5-->4... 1、回溯穷举=...
动态规划典型题目思考1、字符串相关知识2、遍历回文子串的方法3、可以求逆串，然后找最长公共子串 lc 5 之前记长...
动态规划动态规划的基本原理动态规划的运用 1. 动态规划的基本原理 动态规划（Dynamic Programmi...
1. 动态规划算法总结2. 漫画：什么是动态规划？3.算法之动态规划4. 动态规划-算法
从运筹学和算法的角度综合介绍动态规划 算法分类总结动态规划与静态规划的关系浅析静态规划和动态规划动态规划解非线性规...
前言 今天开始学习动态规划，一共有三节，分别是：初识动态规划、动态规划理论、动态规划实战。今天这一节就是初识动态规...
5.动态规划5.1 什么是动态规划？5.2 自底向上的动态规划：5.3 自顶向下的动态规划5.4 0-1背包问题：...
动态规划（Dynamic Programming） 本文包括： 动态规划定义 状态转移方程 动态规划算法步骤 最长...
#动态规划 关于动态规划，先摘一段[wiki][1]的描述： ``` 动态规划（英语：Dynamic progra...
本文标题：[LC]动态规划
本文链接：https://www.haomeiwen.com/subject/yhcwgrtx.html
网友评论