九章算法笔记D1-动态规划概述
@[toc]
D1 动态规划概述
动态规划的组成状态
- 确定状态
- 确定转移方程
- f[x]=min{f[x-2]+1,f[x-5]+1,f[x-7]+1}
- 初始条件和边界情况
- f[0]=0,如果不能拼出Y,f[Y]=正无穷
- 计算顺序
- 一般从小到大(避免重复计算)
最值型-硬币
Problem
你有三种硬币,分别面值2元,5元和7元,每种硬币都有足够多,买一本书需要27元,如何用最少的硬币组合正好付清,不需要对方找钱
1 | // A:{2,5,7} M:27 |
计数型-机器人
Problem
给定m行n列的网格,有一个机器人从左上角(0,0)出发,每一步可以向下或者向右走一步,问有多少种不同的方式走到右下角(m-1,n-1)
1 | public int uniquePaths(int m,int n){ |
存在型-青蛙跳石子
Problem
有n块石头分别在x轴的0,1,。。。,n-1位置.一只青蛙在石头0,像跳到石头n-1。如果青蛙在第i块石头上,他最多可以向右跳距离ai。问青蛙能否跳到石头n-1
Example
1 | Input:a=[2,3,1,1,4] |
1 | public boolean canJump(int[] A){ |
机器人2(坐标型)
Problem
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
1 | public int uniquePathsWithObstacles(int[][] A){ |
leetcode256-粉刷房子(序列型)
题目描述
假如有一排房子,共 n 个,每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种,你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然,因为市场上不同颜色油漆的价格不同,所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的矩阵来表示的。
例如,costs[0][0]
表示第 0 号房子粉刷成红色的成本花费;costs[1][2]
表示第 1 号房子粉刷成绿色的花费,以此类推。请你计算出粉刷完所有房子最少的花费成本。
注意:
所有花费均为正整数。
示例:
输入: [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色,1 号房子粉刷成绿色,2 号房子粉刷成蓝色。
最少花费: 2 + 5 + 3 = 10。
分析
确定状态:
- 不知道房子N-2是什么颜色,就把它记录下来
- 分别记录油漆前N-1栋房子并且房子N-2是红色、蓝色、绿色的最小花费
子问题:设油漆前i栋房子并且房子i-1是红色、蓝色、绿色的最小花费分别为f[i][0]、f[i][1]、f[i][2]
转移方程:
f[i][0]=min{f[i-1][1]+cost[i-1][0],f[i-1][2]+cost[i-1][0]}
f[i][1]=min{f[i-1][0]+cost[i-1][1],f[i-1][2]+cost[i-1][1]}
f[i][2]=min{f[i-1][0]+cost[i-1][2],f[i-1][1]+cost[i-1][2]}
1 | public int minCost(int[][] c){ |
Decode Ways
题意:
有一段由A-Z组成的字母串信息被加密成数字串,加密方式为:A->1,B->2,… ,Z->26,给定加密后的数字串S[0…N-1],问有多少种方式解密成字母串
样例
1 | Input |
分析
状态:设数字串S前i个数字解密成字母串有f[i]种方式
转移方程:设数字串S前i个数字解密成字母串有f[i]种方式
` f[i] = f[i-1]|S[i-1]对应一个字母 + f[i-2]|S[i-2]S[i-1]对应一个字母`
- 数字串S前i个数字解密成字母串的方式数
- 数字串S前i-1个数字解密成字母串的方式数
- 数字串S前i-2个数字解密成字母串的方式数
1 | public int numDecodings(String ss){ |