动态规划-蒲公英云

首先，动态规划不是一个特定的算法，它代表的是一种思想，一种手段
动态规划方法往往用于求解“最优化问题”，能用动态规划求解的问题的前提是问题具有“最优子结构性质”。
最优子结构性质：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。
动态规划的核心是“状态的表达”和“状态转移方程的建立”，状态的意义的确立直接关系到状态转移方程能否建立正确。
动态规划问题常用的有两种方法：
a. “自底向上”的递推。利用“问题的最优解包含子问题的最优解”，由于是“自底向上”求解的，就是说子子问题的最优解已经确立，子问题的最优解就可以从这些子子问题的最优解中确定出来。递推的关键是边界和计算顺序。
b. 记忆化搜索。它是按照“自顶向下”的顺序求解的。与分治法将问题划分为互不相交的子问题不同的是，动态规划用于子问题重叠的情况（不同的子问题具有公共的子子问题），这样就必须要解决“子问题重复计算”的问题，否则会做大量的重复计算，效率急剧下降（就是单纯的搜索，这也就是为什么搜索只能过动态规划问题的一部分测试点的的原因）。记忆化搜索仍按照搜索的过程求解问题，但在搜索的工程中会保存每个子问题的解（用一个数组或散列表）。当需要一个解时，先去检查是否保存过此解，有，直接返回，否则按通常方式计算，并加以保存。注意，搜索可以剪枝！！！

一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。
更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。
记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，

具体问题分析：

1002 数塔取数问题
基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题 收藏  关注
一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。
每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。
   5
  8 4
 3 6 9
7 2 9 5
例子中的最优方案是：5 + 8 + 6 + 9 = 28
Input
第1行：N，N为数塔的高度。(2 <= N <= 500)
第2 - N + 1行：每行包括1层数塔的数字，第2行1个数，第3行2个数......第k+1行k个数。数与数之间用空格分隔（0 <= A[i] <= 10^5) 。
Output
输出最大值
Input示例
4
5
8 4
3 6 9
7 2 9 5
Output示例
28

分析：

1.确定状态：把当前的位置(i,j)看成一个状态，定义状态(i,j)的指标函数d(i,j)为从(i,j)点出发时能得到的最大和（包括(i,j)本身）。在这个状态下，问题解为d(1,1)

确定状态转移方程：从格子(i,j)出发有两种决策。往左走，走到(i+1,j)之后需要求“从(i+1,j)出发能得到的最大和”这一问题，即d(i+1,j)，同样的，往右走，到达(i+1,j+1)后需要求解d(i+1,j+1)这一问题。即状态转移方程为：d(i,j)=a(i,j) + Max{d(i+1,j),d(i+1,j+1)}。数据结构a用于存储输入数据。

具体实现

//用递推来做，相当于一棵二叉树，先确定最底层，然后依次确定上一层，知道第一层。
import java.util.Scanner;

public class Main {

 public static void show(int n,int[][] nums){
     System.out.println("Output trangels:");
     for(int i=1;i<=n;i++){
         for(int j=1;j<=i;j++) System.out.print(nums[i][j]+" ");
         System.out.println();
     }
 }
 public static void main(String[] args) {
     // TODO Auto-generated method stub
     Scanner in = new Scanner(System.in);
     while(in.hasNext()){
         int n = in.nextInt();
         int[][] triangle = new int[n+10][n+10];
         int[][] dp = new int[n+10][n+10];
         for(int i=1;i<=n;i++){
             for(int j=1;j<=i;j++) triangle[i][j] = in.nextInt();
         }
         //最后一层，作为起始边界。
         for(int j=1;j<=n;j++) dp[n][j] = triangle[n][j];
         //向上递推
         for(int i=n-1;i>=1;i--){
             for(int j=1;j<=i;j++){
                 dp[i][j] = triangle[i][j] + Math.max(dp[i+1][j], dp[i+1][j+1]);
             }
         }
         System.out.println(dp[1][1]);
     }
 }

}

//记忆化搜索
import java.util.Arrays;
import java.util.Scanner;

public class Main {

 public static int n;
 public static int[][] dp , triangle;
 public static void show(int n,int[][] nums){
     System.out.println("Output trangels:");
     for(int i=1;i<=n;i++){
         for(int j=1;j<=i;j++) System.out.print(nums[i][j]+" ");
         System.out.println();
     }
 }
 //利用赋值语句的返回值是所赋的值这一特性，将保存dp[i][j]的工作合并到函数的返回语句中。
 public static int memorySearch(int i,int j){
     if(dp[i][j]!=-1) return dp[i][j];
     if(i==n) return triangle[i][j];//搜索到最后一层了
     else return dp[i][j] = triangle[i][j] + Math.max(memorySearch(i+1, j), memorySearch(i+1, j+1));
 }
 public static void main(String[] args) {
     // TODO Auto-generated method stub
     Scanner in = new Scanner(System.in);
     while(in.hasNext()){
         n = in.nextInt();
         triangle = new int[n+10][n+10];
         dp = new int[n+10][n+10];
         //状态-1,代表没有访问过！！
         for(int i=1;i<=n;i++) Arrays.fill(dp[i], -1);
         for(int i=1;i<=n;i++){
             for(int j=1;j<=i;j++) triangle[i][j] = in.nextInt();
         }
         int res = memorySearch(1, 1);
         System.out.println(res);
     }
 }