算法学习笔记_初级

动态规划

求解思路

• 分析特征，分析问题是否可以用动态规划求解（累加的特征），并分析累加规律；
• 状态定义，根据题干分析结果应；该是在一维上面累加，还是在二维上面累加，定义状态为 dp[] 或 dp[][]；
• 转移方程，f(n) 与 f(n - 1) 的关系。

典型题目

斐波那契数列--由0和1开始，之后的斐波那契数就是由之前的两数相加得出。

走方格的方案数

描述 请计算n*m的棋盘格子（n为横向的格子数，m为竖向的格子数）从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。

注：沿棋盘格之间的边缘线行走

数据范围： 1≤n,m≤8

输入描述： 输入两个正整数n和m，用空格隔开。(1≤n,m≤8)

输出描述： 输出一行结果

示例1

输入：2 2
输出：6

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int m = in.nextInt();

			// 找规律：
            // 状态定义 dp[0][0]=0, dp[1][1]=2, dp[1][2]=3, dp[1][3]=4, dp[1][4]=5
            //                                 dp[2][1]=3, dp[3][1]=4, dp[4][1]=5
            //  0  1  2  3  4
            //  1  2  3  4  5
            //  2  3  6  10
            //  3  4  10 20
            //  4  5
            // 
            // 状态定义： dp[0][n] = 1; dp[n][0] = 1;  
            int[][] dp = new int[n + 1][m + 1];

            // 转移方程 f(0,0)=1, f(1,1)=f(1,0)+f(0,1), f(1,2)=f(1,1)+f(0,1)。。。
            for(int i = 0; i < n + 1; i++) {
                for(int j = 0; j < m + 1; j++) {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    }
                }
            }
            
            System.out.println(dp[n][m]);
        }
    }
}

注意：本文归作者所有，未经作者允许，不得转载