动态规划状态转移方程

Leetcode常见DP题状态转移方程一、概述动态规划（Dynamic Programming, DP）是算法设计中的一种常用方法，它通常用于优化递归算法，解决重叠子问题。

Leetcode上有许多经典动态规划问题，而理解状态转移方程是解决这些问题的关键。

本文旨在总结Leetcode常见DP题的状态转移方程，帮助读者更好地理解和掌握动态规划算法的应用。

二、背包问题1. 0-1背包问题问题描述：给定一组物品，每种物品都有重量和价值，要求在限定的总重量下，如何使得所装载的物品总价值最高。

状态转移方程：```dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]), 1 <= i <= n, 1 <= j <= C```其中，dp[i][j]表示前i个物品中最大重量不超过j时的最大价值，weight[i]表示第i个物品的重量，value[i]表示第i个物品的价值，C 表示背包的容量，n为物品的个数。

2. 完全背包问题问题描述：给定一组物品，每种物品都有重量和价值，每种物品不限数量，要求在限定的总重量下，如何使得所装载的物品总价值最高。

状态转移方程：```dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i]] + value[i]), 1 <= i <= n, 1 <= j <= C```其中，dp[i][j]表示前i个物品中最大重量不超过j时的最大价值，weight[i]表示第i个物品的重量，value[i]表示第i个物品的价值，C 表示背包的容量，n为物品的个数。

3. 多重背包问题问题描述：给定一组物品，每种物品都有重量和价值，每种物品有限数量，要求在限定的总重量下，如何使得所装载的物品总价值最高。

状态转移方程：```dp[i][j] = max(dp[i-1][j], dp[i-1][j-k*weight[i]] + k*value[i]), 1 <= i <= n, 1 <= j <= C, 0 <= k <= num[i]```其中，dp[i][j]表示前i个物品中最大重量不超过j时的最大价值，weight[i]表示第i个物品的重量，value[i]表示第i个物品的价值，num[i]表示第i个物品的数量，C表示背包的容量，n为物品的个数。

爬楼梯问题的解题技巧爬楼梯问题是在计算机科学和数学领域经常遇到的一个经典问题。

题目描述如下：假设你正在爬楼梯，楼梯有n级台阶。

每次你可以爬1级台阶或者2级台阶。

请问，你有多少种不同的方法可以爬到楼梯顶部？这个问题可以用递归和动态规划两种方法来解决。

下面我将分别介绍这两种解题技巧。

1. 递归解法：递归解法是最直观的解法，通过将问题分解成更小的子问题来解决。

假设爬到第n级台阶有f(n)种方法，那么可以得到以下递推关系：f(n) = f(n-1) + f(n-2)。

也就是说，爬到第n级台阶的方法数等于爬到第n-1级台阶的方法数加上爬到第n-2级台阶的方法数。

递归解法的代码如下：```pythondef climbStairs(n):if n == 1:return 1if n == 2:return 2return climbStairs(n-1) + climbStairs(n-2)```递归解法的时间复杂度为O(2^n)，因为在每一级台阶上都有两种选择，所以递归树的节点数为指数级别。

虽然递归解法的代码简洁，但是对于大规模的问题，会导致指数级别的计算量，效率较低。

2. 动态规划解法：动态规划是一种将复杂问题分解成简单子问题的解决方法，通过保存子问题的解来避免重复计算，从而提高效率。

对于爬楼梯问题，可以使用动态规划来解决。

我们可以定义一个长度为n+1的数组dp，其中dp[i]表示爬到第i级台阶的方法数。

根据递推关系f(n) = f(n-1) + f(n-2)，可以得到动态规划的状态转移方程：dp[i] = dp[i-1] + dp[i-2]。

初始条件为dp[1] = 1，dp[2] = 2。

动态规划解法的代码如下：```pythondef climbStairs(n):dp = [0] * (n+1)dp[1] = 1dp[2] = 2for i in range(3, n+1):dp[i] = dp[i-1] + dp[i-2]return dp[n]```动态规划解法的时间复杂度为O(n)，因为只需计算n个状态，每个状态的计算只需要常数时间。

1.资源问题1-----机器分配问题F[I,j]:=max(f[i-1,k]+w[i,j-k])2.资源问题2------01背包问题F[I,j]:=max(f[i-1,j-v[i]]+w[i],f[i-1,j]);3.线性动态规划1-----朴素最长非降子序列F[i]:=max{f[j]+1}4.剖分问题1-----石子合并F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]);5.剖分问题2-----多边形剖分F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a[i]);6.剖分问题3------乘积最大f[i,j]:=max(f[k,j-1]*mult[k,i]);7.资源问题3-----系统可靠性(完全背包)F[i,j]:=max{f[i-1,j-c[i]*k]*P[I,x]}8.贪心的动态规划1-----快餐问题F[i,j,k]:=max{f[i-1,j',k']+(T[i]-(j-j')*p1-(k-k')*p2) div p3}9.贪心的动态规划2-----过河f[i]=min{{f(i-k)} (not stone[i]){f(i-k)}+1} (stone[i]); +贪心压缩状态10.剖分问题4-----多边形-讨论的动态规划F[i,j]:=max{正正 f[I,k]*f[k+1,j];负负 g[I,k]*f[k+1,j];正负 g[I,k]*f[k+1,j];负正 f[I,k]*g[k+1,j];} g为min11.树型动态规划1-----加分二叉树 (从两侧到根结点模型)F[I,j]:=max{f[I,k-1]*f[k+1,j]+c[k]}12.树型动态规划2-----选课 (多叉树转二叉树,自顶向下模型)F[I,j]表示以i为根节点选j门功课得到的最大学分f[i,j]:=max{f[t[i].l,k]+f[t[i].r,j-k-1]+c[i]}13.计数问题1-----砝码称重f[f[0]+1]=f[j]+k*w[j];(1<=i<=n; 1<=j<=f[0]; 1<=k<=a[i];)14.递推天地1------核电站问题f[-1]:=1; f[0]:=1;f[i]:=2*f[i-1]-f[i-1-m]15.递推天地2------数的划分f[i,j]:=f[i-j,j]+f[i-1,j-1];16.最大子矩阵1-----一最大01子矩阵f[i,j]:=min(f[i-1,j],v[i,j-1],v[i-1,j-1])+1;ans:=maxvalue(f);17.判定性问题1-----能否被4整除g[1,0]:=true; g[1,1]:=false; g[1,2]:=false; g[1,3]:=false; g[i,j]:=g[i-1,k] and ((k+a[i,p]) mod 4 = j)18.判定性问题2-----能否被k整除f[I,j±n[i] mod k]:=f[i-1,j]; -k<=j<=k; 1<=i<=n20.线型动态规划2-----方块消除游戏f[i,i-1,0]:=0f[i,j,k]:=max{f[i,j-1,0]+sqr(len(j)+k),f[i,p,k+len[j]]+f[p+1,j-1,0]}ans:=f[1,m,0]21.线型动态规划3-----最长公共子串，LCS问题f[i,j]={0(i=0)&(j=0);f[i-1,j-1]+1(i>0,j>0,x[i]=y[j]);max{f[i,j-1]+f[i-1,j]}} (i>0,j>0,x[i]<>y[j]);22.最大子矩阵2-----最大带权01子矩阵O(n^2*m)枚举行的起始，压缩进数列，求最大字段和，遇0则清零23. 资源问题4-----装箱问题(判定性01背包)f[j]:=(f[j] or f[j-v[i]]);24.数字三角形1-----朴素の数字三角形f[i,j]:=max(f[i+1,j]+a[I,j],f[i+1,j+1]+a[i,j]);25.数字三角形2-----晴天小猪历险记之Hill同一阶段上暴力动态规划if[i,j]:=min(f[i,j-1],f[I,j+1],f[i-1,j],f[i-1,j-1])+a[i,j]26.双向动态规划1数字三角形3-----小胖办证f[i,j]:=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j],f[i,j+1]+a[i,j])27. 数字三角形4-----过河卒//边界初始化f[i,j]:=f[i-1,j]+f[i,j-1];28.数字三角形5-----朴素的打砖块f[i,j,k]:=max(f[i-1,j-k,p]+sum[i,k],f[i,j,k]);29.数字三角形6-----优化的打砖块f[I,j,k]:=max{g[i-1,j-k,k-1]+sum[I,k]}30.线性动态规划3-----打鼹鼠’f[i]:=f[j]+1;(abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j])31.树形动态规划3-----贪吃的九头龙⎭⎬⎫⎩⎨⎧======⎭⎬⎫⎩⎨⎧+-++--+=0))2()0(&)0(())1(&)1((1],[]][,[*]0,[],',[]0,',[]][,[*]1,[],1',[]1,',[min ],,[m and j i or j i j i d i p i w k d k j j r f j l f i p i w k d k j j r f j l f k j i f32.状态压缩动态规划1-----炮兵阵地Max(f[Q*(r+1)+k],g[j]+num[k])If (map[i] and plan[k]=0) and((plan[P] or plan[q]) and plan[k]=0)33.递推天地3-----情书抄写员f[i]:=f[i-1]+k*f[i-2]34.递推天地4-----错位排列f[i]:=(i-1)(f[i-2]+f[i-1]);f[n]:=n*f[n-1]+(-1)^(n-2);35.递推天地5-----直线分平面最大区域数f[n]:=f[n-1]+n:=n*(n+1) div 2 + 1;36.递推天地6-----折线分平面最大区域数f[n]:=(n-1)(2*n-1)+2*n;37.递推天地7-----封闭曲线分平面最大区域数f[n]:=f[n-1]+2*(n-1):=sqr(n)-n+2;38递推天地8-----凸多边形分三角形方法数f[n]:=C(2*n-2,n-1) div n;对于k 边形f[k]:=C(2*k-4,k-2) div (k-1); //(k>=3)39递推天地9-----Catalan 数列一般形式1,1,2,5,14,42,132f[n]:=C(2k,k) div (k+1);40递推天地10-----彩灯布置排列组合中的环形染色问题f[n]:=f[n-1]*(m-2)+f[n-2]*(m-1); (f[1]:=m; f[2]:=m(m-1);41线性动态规划4-----找数线性扫描sum:=f[i]+g[j];(if sum=Aim then getout; if sum<Aim then inc(i) else inc(j);)42线性动态规划5-----隐形的翅膀min:=min{abs(w[i]/w[j]-gold)};if w[i]/w[j]<gold then inc(i) else inc(j);43剖分问题5-----最大奖励f[i]:=max(f[i],f[j]+(sum[j]-sum[i])*i-t44最短路1-----Floydf[i,j]:=max(f[i,j],f[i,k]+f[k,j]);ans[q[i,j,k]]:=ans[q[i,j,k]]+s[i,q[i,j,k]]*s[q[i,j,k],j]/s[i,j];45 剖分问题6-----小H 的小屋F[l,m,n]:=f[l-x,m-1,n-k]+S(x,k);46 计数问题2-----陨石的秘密（排列组合中的计数问题）Ans[l1,l2,l3,D]:=f[l1+1,l2,l3,D+1]-f[l1+1,l2,l3,D];F[l1,l2,l3,D]:=Sigma(f[o,p,q,d-1]*f[l1-o,l2-p,l3-q,d]);47 线性动态规划------合唱队形两次F[i]:=max{f[j]+1}＋枚举中央结点48 资源问题------明明的预算方案：加花的动态规划f[i,j]:=max(f[i,j],f[l,j-v[i]-v[fb[i]]-v[fa[i]]]+v[i]*p[i]+v[fb[i]]*p[fb[i]]+v[fa[i]]*p[fa[i]]);49 资源问题-----化工场装箱员[,[1,],[1,]][,,]:min [,[1,],[1,]]1[10,[1,10],[1,10]f n i getA n n i j getB n n i f n i j f n j i getA n n j getB n n j f n i j i getA n n i j j getB n n i j ++++++⎧⎫⎪⎪=+++++++⎨⎬⎪⎪+--+++--+++--⎩⎭-----聚会的快乐f[i,2]:=max(f[i,0],f[i,1]);f[i,1]:=sigma(f[t[i]^.son,0]);f[i,0]:=sigma(f[t[i]^.son,3]);51树形动态规划-----皇宫看守f[i,2]:=max(f[i,0],f[i,1]);f[i,1]:=sigma(f[t[i]^.son,0]);f[i,0]:=sigma(f[t[i]^.son,3]);52递推天地-----盒子与球f[i,1]:=1;f[i,j]:=j*(f[i-1,j-1]+f[i-1,j]);53双重动态规划-----有限的基因序列f[i]:=min{f[j]+1}g[c,i,j]:=(g[a,i,j] and g[b,i,j]) or (g[c,i,j])54最大子矩阵问题-----居住空间f[i,j,k]:=min(min(min(f[i-1,j,k],f[i,j-1,k]),min(f[i,j,k-1],f[i-1,j-1,k])),min(min(f[i-1,j,k-1],f[i,j-1,k-1]),f[i-1,j-1,k-1]))+1;55线性动态规划------日程安排f[i]:=max{f[j]}+P[I]; (e[j]<s[i])56递推天地------组合数C[I,j]:=C[i-1,j]+C[I-1,j-1]C[I,0]:=157树形动态规划-----有向树k中值问题F[I,r,k]:=max{max{f[l[i],I,j]+f[r[i],I,k-j-1]},f[f[l[i],r,j]+f[r[i],r,k-j]+w[I,r]]}58树形动态规划-----CTSC 2001选课F[I,j]:=w[i](if i∈P)+f[l[i],k]+f[r[i],m-k](0≤k≤m)(if l[i]<>0)-----多重历史f[i,j]:=sigma{f[i-k,j-1]}(if checked)60背包问题(+-1背包问题+回溯)-----CEOI1998 Substractf[i,j]:=f[i-1,j-a[i]] or f[i-1,j+a[i]]61线性动态规划(字符串)-----NOI 2000 古城之谜f[i,1,1]:=min{f[i+length(s),2,1],f[i+length(s),1,1]+1}f[i,1,2]:=min{f[i+length(s),1,2]+words[s],f[i+length(s),1,2]+words[s]}62线性动态规划-----最少单词个数f[i,j]:=max{f[I,j],f[u-1,j-1]+l}63线型动态规划-----APIO2007 数据备份状态压缩＋剪掉每个阶段j前j*2个状态和j*2+200后的状态贪心动态规划f[i]:=min(g[i-2]+s[i],f[i-1]);64树形动态规划-----APIO2007 风铃f[i]:=f[l]+f[r]+{1 (if c[l]<c[r])}g[i]:=1(d[l]<>d[r]) 0(d[l]=d[r])g[l]=g[r]=1 then Halt;65地图动态规划-----NOI 2005 adv19910F[t,i,j]:=max{f[t-1,i-dx[d[[t]],j-dy[d[k]]]+1],f[t-1,i,j];66地图动态规划-----优化的NOI 2005 adv19910F[k,i,j]:=max{f[k-1,i,p]+1} j-b[k]<=p<=j;67目标动态规划-----CEOI98 subtraF[I,j]:=f[I-1,j+a[i]] or f[i-1,j-a[i]]68目标动态规划----- Vijos 1037搭建双塔问题F[value,delta]:=g[value+a[i],delta+a[i]] or g[value,delta-a[i]]69树形动态规划-----有线电视网f[i,p]:=max(f[i,p],f[i,p-q]+f[j,q]-map[i,j])leaves[i]>=p>=l, 1<=q<=p;70地图动态规划-----vijos某题F[I,j]:=min(f[i-1,j-1],f[I,j-1],f[i-1,j]);71最大子矩阵问题-----最大字段和问题f[i]:=max(f[i-1]+b[i],b[i]); f[1]:=b[1]72最大子矩阵问题-----最大子立方体问题枚举一组边i的起始，压缩进矩阵 B[I,j]+=a[x,I,j]枚举另外一组边的其实，做最大子矩阵73括号序列-----线型动态规划f[I,j]:=min(f[I,j],f[i+1,j-1](s[i]s[j]=”()”or(”[]”)),f[I+1,j+1]+1 (s[j]=”(”or”[” ] , f[I,j-1]+1(s[j]=”)”or”]” )74棋盘切割-----线型动态规划f[k,x1,y1,x2,y2]=min{min{f[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2],f[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2]min{}}75概率动态规划-----聪聪和可可(NOI2005)x:=p[p[i,j],j]f[I,j]:=(f[x,b[j,k]]+f[x,j])/(l[j]+1)+1f[I,i]=0f[x,j]=176概率动态规划-----血缘关系F[A, B]=(f[A0, B]+P[A1, B])/2f[I,i]=1f[I,j]=0(I,j无相同基因)77线性动态规划-----决斗F[I,j]=(f[I,j] and f[k,j]) and (e[I,k] or e[j,k]),i<k<j78线性动态规划-----舞蹈家F[x,y,k]=min(f[a[k],y,k+1]+w[x,a[k]],f[x,a[k],k+1]+w[y,a[k]])79线性动态规划-----积木游戏F[I,a,b,k]=max(f[I,a+1,b,k],f[i+1,a+1,a+1,k’],f[I,a+1,a+1,k’])80树形动态规划（双次记录）-----NOI2003 逃学的小孩朴素的话枚举节点i和离其最远的两个节点 j,k O(n^2)每个节点记录最大的两个值，并记录这最大值分别是从哪个相邻节点传过来的。

转载-夜深⼈静写算法（⼆）-动态规划【例题7】给定⼀个长度为n（n <= 1000）的字符串A，求插⼊最少多少个字符使得它变成⼀个回⽂串。

典型的区间模型，回⽂串拥有很明显的⼦结构特征，即当字符串X是⼀个回⽂串时，在X两边各添加⼀个字符'a'后，aXa仍然是⼀个回⽂串，我们⽤d[i][j]来表⽰A[i...j]这个⼦串变成回⽂串所需要添加的最少的字符数，那么对于A[i] == A[j]的情况，很明显有 d[i][j] = d[i+1][j-1] （这⾥需要明确⼀点，当i+1 > j-1时也是有意义的，它代表的是空串，空串也是⼀个回⽂串，所以这种情况下d[i+1][j-1] = 0）；当A[i] != A[j]时，我们将它变成更⼩的⼦问题求解，我们有两种决策：1、在A[j]后⾯添加⼀个字符A[i]；2、在A[i]前⾯添加⼀个字符A[j]；根据两种决策列出状态转移⽅程为：d[i][j] = min{ d[i+1][j], d[i][j-1] } + 1; (每次状态转移，区间长度增加1)空间复杂度O(n^2)，时间复杂度O(n^2)，下⽂会提到将空间复杂度降为O(n)的优化算法。

3、背包模型背包问题是动态规划中⼀个最典型的问题之⼀。

由于⽹上有⾮常详尽的背包讲解，这⾥只将常⽤部分抽出来，具体推导过程详见。

a.0/1背包有N种物品（每种物品1件）和⼀个容量为V的背包。

放⼊第 i 种物品耗费的空间是Ci，得到的价值是Wi。

求解将哪些物品装⼊背包可使价值总和最⼤。

f[i][v]表⽰前i种物品恰好放⼊⼀个容量为v的背包可以获得的最⼤价值。

决策为第i个物品在前i-1个物品放置完毕后，是选择放还是不放，状态转移⽅程为：f[i][v] = max{ f[i-1][v], f[i-1][v - Ci] +Wi }时间复杂度O(VN)，空间复杂度O(VN) （空间复杂度可利⽤滚动数组进⾏优化达到O(V)，下⽂会介绍滚动数组优化）。

动态规划的状态转移方程动态规划是一种常用的求解最优化问题的方法，广泛应用于计算机科学、数学和经济学等领域。

在动态规划中，状态转移方程是关键步骤，它描述了问题的状态如何从一个状态转移到下一个状态。

本文将详细介绍动态规划的状态转移方程及其应用。

一、动态规划的基本原理动态规划是一种将复杂问题分解成更小且重叠的子问题来求解的方法。

它的基本思想是利用已经计算过的子问题的解来求解当前问题的解，从而避免重复计算，提高计算效率。

二、状态转移方程的定义状态转移方程是动态规划中的重要概念，它描述了问题的状态如何从一个阶段转移到下一个阶段。

状态转移方程通常使用递推的方式来表示，即通过已知状态推导出未知状态。

在解决最优化问题时，我们通常需要定义一个目标函数，通过优化目标函数来求解最优解。

状态转移方程可以将目标函数从一个阶段递推到另一个阶段，从而求解出最优解。

三、状态转移方程的形式状态转移方程的形式可以根据具体问题的特点灵活定义。

一般来说，状态转移方程包括以下几个要素：1. 状态的定义：将问题划分为若干个阶段，并定义每个阶段的状态。

状态可以是一个变量、一个数组或其他数据结构。

2. 状态转移的定义：描述问题的状态如何从一个阶段转移到下一个阶段。

状态转移可以使用数学表达式、递归方程或其他形式表示。

3. 初始状态和边界条件：确定问题的起始状态和终止状态，并定义边界条件。

四、举例说明以经典的背包问题为例，我们来看一下如何使用状态转移方程解决问题。

背包问题是一个经典的组合优化问题，给定一个背包的容量和一组物品，每个物品有一个重量和一个价值，需要选择一些物品放入背包中，使得背包的总重量不超过容量，且总价值最大。

在解决背包问题时，我们可以将其划分为若干个阶段，每个阶段表示选择第i个物品放入背包的决策。

我们可以定义一个二维数组dp[i][j]来表示在前i个物品中，背包容量为j时的最大价值。

状态转移方程可以表示为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])其中，dp[i-1][j]表示不选择第i个物品时的最大价值，dp[i-1][j-w[i]] + v[i]表示选择第i个物品时的最大价值。

最短路径问题的动态规划算法最短路径问题的动态规划算法是一种常用的解决路径优化的方法。

动态规划算法的核心思想是将原问题拆分成若干个子问题，通过递推关系找到最优解。

在最短路径问题中，我们通常希望找到从起点到终点的最短路径。

首先，我们需要定义一个二维数组dp，其中dp[i][j]表示从起点到达坐标(i, j)的最短路径长度。

初始化dp数组，将起点的值设为0，其他位置的值设为无穷大（即表示不可达）。

接下来，我们需要确定动态规划的状态转移方程。

对于任意一个坐标(i, j)，它可以从上方的坐标(i-1, j)、左方的坐标(i, j-1)、右方的坐标(i, j+1)、下方的坐标(i+1, j)四个位置中的某一个到达。

因此，可以得到状态转移方程如下：
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i][j+1], dp[i+1][j]) + 1
其中，min表示取其中的最小值。

通过以上状态转移方程，我们可以逐步更新dp数组，直到最终得到终点的最短路径长度。

需要注意的是，动态规划算法的时间复杂度通常是O(n^2)，其中n 表示问题规模。

因此，在处理大规模最短路径问题时，需要考虑算法的效率，可能需要进行剪枝等优化操作。

总的来说，最短路径问题的动态规划算法在路径优化领域有着重要的应用价值，通过合理定义状态转移方程和优化算法效率，可以找到从起点到终点的最短路径长度，为路径规划提供有效的解决方案。

例谈四种常见的动态规划模型动态规划是解决多阶段决策最优化问题的一种思想方法，本文主要结合一些例题，把一些常见的动态规划模型，进行归纳总结。

（一）、背包模型可用动态规划解决的背包问题，主要有01背包和完全背包。

对于背包的类型，这边就做个简单的描述：n个物品要放到一个背包里，背包有个总容量m，每个物品都有一个体积w[i]和价值v[i]，问如何装这些物品,使得背包里放的物品价值最大。

这类型的题目，状态表示为：f[j]表示背包容量不超过j时能够装的最大价值，则状态转移方程为：f[j]:=max{f[j-w[i]]+v[i]},边界：f[0]:=0;简单的程序框架为：beginreadln(m,n);for i:=1 to n do readln(w[i],v[i]);f[0]:=0;for i:=1 to m dofor j:=1 to n dobeginif i>=w[j] then t:=f[i-w[j]]+v[j];if t>f[i] then f[i]:=t;end;writeln(f[m]);end.这类型的题目应用挺广的（noip1996提高组第4题，noip2001普及组装箱问题，noip2005普及组采药等），下面一个例子，也是背包模型的简单转化。

货币系统(money)【问题描述】母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统。

他们对货币的数值感到好奇。

传统地，一个货币系统是由1，5，10，20或25，50，100的单位面值组成的。

母牛想知道用货币系统中的货币来构造一个确定的面值，有多少种不同的方法。

使用一个货币系统{1,2,5,10,..}产生18单位面值的一些可能的方法是:18×1,9×2,8×2+2×1,3×5+2+1等等其它。

写一个程序来计算有多少种方法用给定的货币系统来构造一个确定的面值。

【输入格式】货币系统中货币的种类数目是v(1≤v≤25)；要构造的面值是n(1≤n≤10,000)；第1行:二个整数，v和n；第2..v+1行：可用的货币v个整数(每行一个)。

动态规划问题-经典模型的状态转移⽅程状态转移⽅程动态规划中当前的状态往往依赖于前⼀阶段的状态和前⼀阶段的决策结果。

例如我们知道了第i个阶段的状态Si以及决策Ui，那么第i+1阶段的状态Si+1也就确定了。

所以解决动态规划问题的关键就是确定状态转移⽅程，⼀旦状态转移⽅程确定了，那么我们就可以根据⽅程式进⾏编码。

在前⾯的⽂章讲到了如何设计⼀个动态规划算法，有以下四个步骤：1、刻画⼀个最优解的结构特征。

2、递归地定义最优解的值。

3、计算最优解的值，通常采⽤⾃底向上的⽅法。

4、利⽤计算出的信息构造⼀个最优解。

对于确定状态转移⽅程就在第⼀步和第⼆步中，⾸先要确定问题的决策对象，接着对决策对象划分阶段并确定各个阶段的状态变量，最后建⽴各阶段的状态变量的转移⽅程。

例如⽤dp[i]表⽰以序列中第i个数字结尾的最长递增⼦序列长度和最长公共⼦序列中⽤dp[i][j]表⽰的两个字符串中前 i、 j 个字符的最长公共⼦序列，我们就是通过对这两个数字量的不断求解最终得到答案的。

这个数字量就被我们称为状态。

状态是描述问题当前状况的⼀个数字量。

⾸先，它是数字的，是可以被抽象出来保存在内存中的。

其次，它可以完全的表⽰⼀个状态的特征，⽽不需要其他任何的辅助信息。

最后，也是状态最重要的特点，状态间的转移完全依赖于各个状态本⾝，如最长递增⼦序列中，dp[x]的值由 dp[i](i < x)的值确定。

若我们在分析动态规划问题的时候能够找到这样⼀个符合以上所有条件的状态，那么多半这个问题是可以被正确解出的。

所以说，解动态规划问题的关键，就是寻找⼀个好的状态。

总结下⾯对这⼏天的学习总结⼀下，将我遇到的各种模型的状态转移⽅程汇总如下：1、最长公共⼦串假设两个字符串为str1和str2，它们的长度分别为n和m。

d[i][j]表⽰str1中前i个字符与str2中前j个字符分别组成的两个前缀字符串的最长公共长度。

这样就把长度为n的str1和长度为m的str2划分成长度为i和长度为j的⼦问题进⾏求解。

状态转移方程状态转移方程。

状态转移方程。

是动态规划中本阶段的状态往往是上一阶段状态和上一阶段决策的结果。

如果给定了第K阶段的状态Sk以及决策uk。

则第K+1阶段的状态Sk+1也就完全确定。

中文名,状态转移方程。

应用学科,编程。

适用领域范围,DP问题。

适用领域范围,动态规划算法。

定义。

动态规划中本阶段的状态往往是上一阶段状态和上一阶段决策的结果。

如果给定了第K阶段的状态Sk以及决策uk,则第K+1阶段的状态Sk+1也就完全确定。

状态也就是说Sk+1与Sk,uk之间存在一种明确的数量对应关系。

记为Tk,即有Sk+1= Tk。

这种用函数表示前后阶段关系的方程。

称为状态转移方程。

在上例中状态转移方程为Sk+1= uk 。

设计。

任何思想方法都有一定的局限性。

超出了特定条件。

它就失去了作用。

同样。

动态规划也并不是万能的。

适用动态规划的问题必须满足最优化原理和无后效性。

1.最优化原理最优化原理可这样阐述：一个最优化策略具有这样的性质。

不论过去状态和决策如何。

对前面的决策所形成的状态而言。

余下的诸决策必须构成最优策略。

简而言之。

一个最优化策略的子策略总是最优的。

一个问题满足最优化原理又称其具有最优子结构性质。

2.无后效性将各阶段按照一定的次序排列好之后。

对于某个给定的阶段状态。

它以前各阶段的状态无法直接影响它未来的决策。

而只能通过当前的这个状态。

换句话说。

每个状态都是过去历史的一个完整总结。

这就是无后向性。

又称为无后效性。

3.子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。

其中的关键在于解决冗余。

这是动态规划算法的根本目的。

动态规划实质上是一种以空间换时间的技术。

它在实现的过程中。

不得不存储产生过程中的各种状态。

所以它的空间复杂度要大于其它的算法。

如果满足上述条件。

一般可以按照以下步骤进行设计：一。

确定问题的决策对象二。

对决策对象划分阶段三。

对各阶段确定状态变量四。

状态-状态转移方程状态转移方程。

状态转移方程。

是动态规划中本阶段的状态往往是上一阶段状态和上一阶段决策的结果。

如果给定了第K阶段的状态Sk以及决策uk。

则第K+1阶段的状态Sk+1也就完全确定。

中文名,状态转移方程。

应用学科,编程。

适用领域范围,DP问题。

适用领域范围,动态规划算法。

定义。

动态规划中本阶段的状态往往是上一阶段状态和上一阶段决策的结果。

如果给定了第K阶段的状态Sk以及决策uk,则第K+1阶段的状态Sk+1也就完全确定。

状态也就是说Sk+1与Sk,uk 之间存在一种明确的数量对应关系。

记为Tk,即有Sk+1= Tk。

这种用函数表示前后阶段关系的方程。

称为状态转移方程。

在上例中状态转移方程为Sk+1= uk 。

设计。

任何思想方法都有一定的局限性。

超出了特定条件。

它就失去了作用。

同样。

动态规划也并不是万能的。

适用动态规划的问题必须满足最优化原理和无后效性。

1.最优化原理最优化原理可这样阐述：一个最优化策略具有这样的性质。

不论过去状态和决策如何。

对前面的决策所形成的状态而言。

余下的诸决策必须构成最优策略。

简而言之。

一个最优化策略的子策略总是最优的。

一个问题满足最优化原理又称其具有最优子结构性质。

2.无后效性将各阶段按照一定的次序排列好之后。

对于某个给定的阶段状态。

它以前各阶段的状态无法直接影响它未来的决策。

而只能通过当前的这个状态。

换句话说。

每个状态都是过去历史的一个完整总结。

这就是无后向性。

又称为无后效性。

3.子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。

其中的关键在于解决冗余。

这是动态规划算法的根本目的。

动态规划实质上是一种以空间换时间的技术。

它在实现的过程中。

不得不存储产生过程中的各种状态。

所以它的空间复杂度要大于其它的算法。

如果满足上述条件。

一般可以按照以下步骤进行设计：一。

确定问题的决策对象二。

对决策对象划分阶段三。

对各阶段确定状态变量四。

分组背包问题常见解法
常见的解法包括动态规划和状态压缩。

动态规划解法：
1. 定义`dp[i][j]`表示前i个物品选择j个分组所能获得的最大价值。

2. 初始化`dp`数组为0。

3. 设置状态转移方程为`dp[i][j] = max(dp[i-1][j], dp[i-1][j-group[i].size] + value[i])`，其中`group[i].size`表示第i个物品所属的分组包含的物品数量，`value[i]`表示第i个物品的价值。

4. 依次考虑物品和分组，更新`dp`数组。

5. 最终结果为`dp[n][m]`，其中n表示物品的个数，m表示分组的个数。

状态压缩解法：
1. 定义一个一维数组`dp`表示前i个物品选择j个分组所能获得的最大价值。

2. 初始化`dp`数组为0。

3. 设置状态转移方程为`dp[j] = max(dp[j], dp[j-group[i].size] + value[i])`，其中`group[i].size`表示第i个物品所属的分组包含的物品数量，`value[i]`表示第i个物品的价值。

4. 依次考虑物品和分组，更新`dp`数组。

5. 最终结果为`dp[m]`，其中m表示分组的个数。

例1 求解下列整数规划得最优解:()123123max 45634510..01,2,3,j j Z x x x x x x s t x j x =++++⎧⎪⎨=⎪⎩≤≥为整数.解 （1）建立动态规划模型:阶段变量: 将给每一个变量 赋值瞧成一个阶段, 划分为3个阶段, 且阶段变量k=1,2,3. 设状态变量 表示从第 阶段到第3阶段约束右端最大值, 则 设决策变量k x 表示第k 阶段赋给变量k x 得值(1,2,3)k =、 状态转移方程: 阶段指标: 基本方程；()(){}()3113,2,1044()max ,()0.s k k k k k k k k k k x a f s u s x f s f s ++⎡⎤=⎢⎥⎢⎥⎣⎦⎧=+⎪⎨⎪=⎩≤≤ 其中1233,4, 5.a a a === 用逆序法求解: 当3k =时，()(){}{}33333443330055max 6max 6,ssx x f s x f s x ⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦=+=≤≤≤而 表示不超过 得最大整数。

因此, 当 时, ；当 时, 可取0或1；当 时, 可取0, 1, 2,由此确定 现将有关数据列入表4.1中当 时, 有()(){}(){}22222332322220044max 5max 54,ssx x f s xf s xf s x ⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦=+=+-≤≤≤≤而 。

所以当 时, ；当 时, ；当 时 。

由此确定 。

现将有关数据列入表4.2中、当时,有()(){}(){}11111221211110033max 4max 43,ssx x f s x f s x f s x ⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦=+=+-≤≤≤≤例5 用动态规划方法解下列非线性规划问题⎩⎨⎧=≥≤++⋅⋅=3,2,1 0 max 3213221i x c x x x x x x z i 解: 解决这一类静态规划问题, 需要人为地赋予时间概念, 从而将该问题转化为多阶段决策过程。

动态转移方程推导过程动态转移方程是动态规划算法中的核心部分，用于描述问题的状态转移情况。

动态转移方程的推导过程一般可以分为以下三个步骤：定义状态、推导状态转移方程、确定边界条件。

第一步，定义状态。

在动态规划算法中，状态通常是描述问题的解的情况。

因此，定义状态需要考虑如何描述问题的解，以及解与原问题之间的关系。

一般来说，状态可以是一个数值、一个矩阵、一个序列等，具体根据问题的特点而定。

例如，在求解最长上升子序列的问题中，状态可以是以第i个元素为结尾的最长上升子序列的长度。

第二步，推导状态转移方程。

状态转移方程描述当前状态与下一个状态之间的转移情况。

因此，状态转移方程的推导需要考虑当前状态与下一个状态之间的关系。

状态转移方程通常可以通过以下两种方式推导：递推和记忆化搜索。

递推是从小规模问题的解开始递推到大规模问题的解，而记忆化搜索则是从大规模问题的解开始逐步缩小到小规模问题的解。

例如，在求解最长上升子序列的问题中，可以通过递推方式推导状态转移方程：dp[i]=max(dp[j])+1，其中j<i且a[j]<a[i]，表示前i个元素的最长上升子序列长度等于前j个元素的最长上升子序列长度加1。

第三步，确定边界条件。

边界条件通常是问题规模小到无法继续递推或搜索时得到的解，也就是问题的最小解。

边界条件在动态规划算法中非常重要，因为它们决定了算法的终止条件。

在一些问题中，边界条件比较简单，例如最长上升子序列的边界条件可以是dp[0]=1。

在一些问题中，边界条件可能不止一组，需要考虑多种情况。

总之，动态转移方程是动态规划算法中的核心部分，它描述了问题的状态转移情况。

动态转移方程的推导过程需要根据问题的特点来确定状态、推导状态转移方程并确定边界条件。

在实际应用中，需要对不同类型的问题进行分类，使用相应的算法模板来解决。

最长子序列状态转移方程最长子序列是指在一个序列中，找到一个子序列，使得该子序列的元素在原序列中的相对顺序保持不变，并且该子序列的长度最长。

求解最长子序列问题是动态规划中的一个经典问题，可以通过状态转移方程来解决。

假设我们有两个序列A和B，长度分别为n和m。

我们定义一个二维数组dp，其中dp[i][j]表示序列A的前i个元素和序列B的前j个元素的最长子序列的长度。

接下来，我们来推导最长子序列的状态转移方程。

当i=0或j=0时，dp[i][j]的值为0，因为其中一个序列为空，无法构成子序列。

当A[i]等于B[j]时，说明A的第i个元素和B的第j个元素相等，那么dp[i][j]的值可以通过dp[i-1][j-1]加1得到，即dp[i][j] = dp[i-1][j-1] + 1。

当A[i]不等于B[j]时，说明A的第i个元素和B的第j个元素不相等，那么dp[i][j]的值可以通过dp[i-1][j]和dp[i][j-1]中的较大值得到，即dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

综上所述，最长子序列的状态转移方程可以表示为：dp[i][j] = 0, 当i=0或j=0dp[i][j] = dp[i-1][j-1] + 1, 当A[i]等于B[j]dp[i][j] = max(dp[i-1][j], dp[i][j-1]), 当A[i]不等于B[j]通过使用这个状态转移方程，我们可以逐步计算出dp数组中的所有元素，最终得到最长子序列的长度。

除了最长子序列的长度，我们还可以通过回溯的方式找到最长子序列本身。

具体方法是从dp[n][m]开始，根据dp数组的值和状态转移方程，逆向推导出最长子序列的元素。

最长子序列状态转移方程是解决最长子序列问题的关键，它将问题分解为子问题，并通过动态规划的方式逐步求解。

通过理解和应用这个状态转移方程，我们可以高效地解决最长子序列问题，提高算法的效率。

DP动态规划单库发电优化调度DP（Dynamic Programming）动态规划是一种常用的解决优化问题的方法，可以帮助我们找到最优解。

在单库发电优化调度问题中，我们需要合理安排电力的发电方案以满足需求，并使得总成本最小。

下面我们将介绍如何使用DP动态规划来解决这个问题。

首先，让我们来定义一些变量和参数：-N：时间段的总数，每个时间段记为i（1≤i≤N）。

- demand[i]：第 i 个时间段的电力需求。

- cost[i]：第 i 个时间段的发电成本。

- dp[i]：在前 i 个时间段内的最小总成本。

接下来，我们来定义DP状态转移方程。

对于任意的i（1≤i≤N），我们有以下状态转移方程：- dp[i] = min(dp[j] + cost[i] * (demand[i] - demand[j] + K) * (demand[i] - demand[j] + K) + F)其中，j是在i之前的一个时间段。

K是一个常数，用于调整发电成本和电力需求之间的关系。

F是固定成本，不随电力发生变化。

在状态转移方程中，dp[j] 表示在前 j 个时间段内的最小总成本。

cost 是发电成本，demand 是电力需求。

公式中的两项 (demand[i] - demand[j] + K) * (demand[i] - demand[j] + K) 用于衡量每个时间段内发电与需求之间的差异，并乘以发电成本。

F 是固定成本。

我们可以使用动态规划的方法来计算所有的 dp[i]。

具体步骤如下：1. 初始化 dp[0] = 0。

2.对于每个i（1≤i≤N）：- 初始化dp[i] = ∞。

-对于每个j（0≤j<i）：- 计算当前状态下的总成本，即：cost[i] * (demand[i] -demand[j] + K) * (demand[i] - demand[j] + K) + F。

- 更新 dp[i] 为 dp[j] + 当前状态下的总成本。

dp状态转移方程
DP（动态规划）状态转移方程是一种常用的算法思想，可以用来解决很多实际问题。

在DP算法中，状态转移方程是至关重要的一部分，它用来描述如何从一个状态转移到另一个状态。

DP状态转移方程通常可以用以下公式表示：
dp[i] = f(dp[i-1], dp[i-2], ..., dp[i-k])
其中，dp[i] 表示状态 i 的最优解，f 表示状态转移方程，k 表示转移的步长。

在实际问题中，状态转移方程的形式和具体实现方法都有很大的差别，需要根据具体问题进行调整和优化。

但是，通常状态转移方程都具有以下特点：
1. 最优子结构性质
即问题的最优解包含子问题的最优解。

这个特点是DP算法的核心，也是状态转移方程的基础。

2. 无后效性
即某个状态一旦确定，就不受之后决策的影响。

这个特点是DP 算法的前提条件，也是状态转移方程的基础。

3. 重叠子问题性质
即子问题之间存在重叠。

这个特点是DP算法的优势，可以通过记忆化搜索等方法进行优化。

总之，DP状态转移方程是一种非常重要的算法思想，在实际问题中发挥着巨大的作用。

熟练掌握状态转移方程的原理和应用方法，
对于提高算法竞赛和面试的能力都非常有帮助。

最大连续子序列求和如何设置状态转移方程
最大连续子序列求和是一个经典的动态规划问题，其状态转移方程设置如下：
假设当前最大子序列和为max_sum，当前子序列的结尾位置为end，当前子序列的起始位置为start，那么有以下三种情况：
1. 如果当前位置i小于起始位置start，则最大子序列和为max_sum。

2. 如果当前位置i大于结尾位置end，则最大子序列和为当前位置i的值。

3. 如果当前位置i在子序列范围内，则最大子序列和为当前位置i的值加上起始位置start到当前位置i之间的最大子序列和。

根据以上分析，我们可以设置状态转移方程如下：
max_sum[i] = max(max_sum[start], current_sum + nums[i])
其中，max_sum[i]表示当前位置i的最大子序列和，current_sum表示起始位置start到当前位置i之间的最大子序列和，nums[i]表示当前位置i的值，start表示当前子序列的起始位置，end表示当前子序列的结尾位置。

我们可以使用一个数组来保存每个位置的最大子序列和，然后从前往后遍历数组，更新每个位置的最大子序列和。

最后，返回数组的最后一个元素即为最大连续子序列和。